Description

There are 2002 persons. Now we want to investigate the relationship between them. We choose N persons for investigation, and their numbers are from 0 to N-1. Next, we will investigate the relationship between any two given persons. Assume that if person a and person b are friends, the friends of person a and the friends of person b will also be friends.

 

We provide with the following partial code and ask you to complete get_ga, get_gb, and set_friend_ab functions:

#include<stdio.h>
#include<stdbool.h>
#define MAXN 2005

bool f[MAXN][MAXN];
int n;

void init(){
      int i=0,j;
      for(;i<n;++i){
            for(j=0;j<n;++j){
                  f[i][j]=false;
            }
            f[i][i]=true;
      }
}

bool is_friend(int a,int b){
      //if f[a][b]=true, person a and person b are friends.
      return f[a][b];
}

int ga[MAXN],gb[MAXN];
int len_ga,len_gb;

void get_ga(int a){
      //Array ga saves all the friends of person a.
      //For example, if all the friends of person a are 1, 4, 5 and 10,
      //ga[]={1,4,5,10}, len_ga=4.
      //Please think how to get Array ga according to 2D Array f.
}

void get_gb(int b){
      //Array gb saves all the friends of person b.
      //Similar to get_ga().
}

void set_friend_ab(){
      //Now you have Array ga and gb.
      //Because person a and b will be friends,
      //how to use Array ga and gb for updating 2D Array f?
}

void merge_friend(int a,int b){
      if(is_friend(a,b)) return;
      get_ga(a);
      get_gb(b);
      set_friend_ab();
}

int main(){
      int t,q;
      scanf("%d",&t);
      while(t--){
            scanf("%d%d",&n,&q);
            init();
            while(q--){
                  int op,a,b;
                  scanf("%d%d%d",&op,&a,&b);
                  if(op==1) puts(is_friend(a,b) ? "they are friends!" : "they are not friends!");
                  else merge_friend(a,b);
            }
      }
      return 0;
}

Input

There is a number t in the first line, indicating that there are t test cases. Next, there are two numbers, N and Q, in each test case, indicating that we will investigate N persons, followed by Q instructions. Every instruction consists of 3 numbers, P, a and b. If P=0, it shows that person a and person b are friends. If P=1, we have to judge whether person a and person b are friends according to the given information.

Notice that:

(1) 0<=a,b<N

(2) a!=b

(3) 0<Q<=10^5

(4) 0<N<=2000

Output

For every instruction P=1, if a and b are friends, please print "they are friends!". If they are not, print "they are not friends!". Remember to add '\n' in the end of every output.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss