The most delicate thing is to arrange seats for the guests. In any case, you can't put two rivals at the same banquet table! This arduous task is now up to you. For any pair of guests, please write a program to tell the host whether they can be arranged at the same table.

Input format:

Enter the first line to give three positive integers: n (≤ 100), that is, the total number of guests who come to the banquet, then these people are numbered from 1 to N; M is the number of known relationships between the two guests; K is the number of queries. Then line M, each line gives a relationship between a pair of guests, the format is: guest 1 guest 2 relationship, where relationship 1 is a friend, and - 1 is a dead partner. Note that two people cannot be both friends and enemies. Finally, K lines, each line gives a pair of guest numbers to be queried.

Let's assume that a friend's friend is also a friend. But enemies of enemies are not necessarily friends, nor enemies of friends. Only a simple and direct hostile relationship is absolutely impossible.

Output format:

Output a row of results for each query: if two guests are friends and have no hostile relationship, output No problem; if they are not friends but are not hostile, output OK; if they are hostile but have common friends, output OK but...; if they only have hostile relationship, output No way.

Input example:

7 8 4
5 6 1
2 7 -1
1 3 1
3 4 1
6 7 -1
1 2 1
1 4 1
2 3 -1
3 4
5 7
2 3
7 2

Output example:

No problem
OK
OK but...
No way

Author: Chen Yue

Setting: Zhejiang University

Time limit: 200 ms

Memory limit: 64 MB

Code length limit: 16 KB

Train of thought:

Put the numbers of people who are friends with each other in a set (i.e. circle of friends), and use a two-dimensional array to record the relationship between two people (whether they are enemies or not). If they are enemies, it is recorded as - 1, otherwise it is 0;

Finally, according to these two points (four states) to judge the relationship between any two people can be:

1. In a circle of friends and not enemies

2. Not in a circle of friends and not an enemy

3. In a circle of friends and enemies < = = > ok but

4. Not in a circle of friends and enemies

And look up the correlation function of the set:

1. Initialization function:

void init()
{
   for(int i=1;i<=n;i++){
        pre[i]=i;//Each person's last person's number is initialized to their own number
   }
}

2. Follow function:

int findRoot(int x)
{
    if(pre[x]==x){//If the top-level root node is found, its number will be returned as the root node number of the current node
        return x;
    }
    return findRoot(pre[x]);//Otherwise, keep looking up to find the top root node
}

3. Merge function:

void merge(int x,int y)
{
    int px=findRoot(x);//Find the root of x
    int py=findRoot(y);//Find the root of y
    if(px!=py){//If x and y root nodes are different, that is, they are not in a set, they are combined into a set (that is, let the root node of one point be equal to the root node of another (that is, connect one root node to another root node))
        pre[px]=py;
    }
}

Full code:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
int n,m,k;
int a[110][110],pre[110];

//Initialization function
void init()
{
   for(int i=1;i<=n;i++){
        pre[i]=i;//Each person's last person's number is initialized to their own number
   }
}

//Root finding function
int findRoot(int x)
{
    if(pre[x]==x){//If the top-level root node is found, its number will be returned as the root node number of the current node
        return x;
    }
    return findRoot(pre[x]);//Otherwise, keep looking up to find the top root node
}

//Merging function
void merge(int x,int y)
{
    int px=findRoot(x);//Find the root of x
    int py=findRoot(y);//Find the root of y
    if(px!=py){//If x and y root nodes are different, that is, they are not in a set, they are combined into a set (that is, let the root node of one point be equal to the root node of another (that is, connect one root node to another root node))
        pre[px]=py;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>k;
    init();
    while(m--){
        int x,y,z;
        cin>>x>>y>>z;
        if(z==-1){
            a[x][y]=a[y][x]=-1;
        }
        else{
            merge(x,y);
        }
    }
    while(k--){
        int u,v;
        cin>>u>>v;
        if(findRoot(u)==findRoot(v)&&!a[u][v]){
            cout<<"No problem"<<endl;
        }
        else if(findRoot(u)!=findRoot(v)&&!a[u][v]){
            cout<<"OK"<<endl;
        }
        else if(findRoot(u)==findRoot(v)&&a[u][v]){
            cout<<"OK but..."<<endl;
        }
        else{
            cout<<"No way"<<endl;
        }
    }
    return 0;
}