1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <set> 5 #include <algorithm> 6 #include <map> 7 #include <queue> 8 #include<vector> 9 #define maxn 10001010 #define maxm 10001011 #define mod 100000000000000000012 #define INF 0x3fffffff13 using namespace std;14 int father[maxn];15 int n;16 int d[maxn];17 void init(){18     for(int i=0;i<=n;++i){19         father[i]=i;20         d[i]=-1;21     }22 }23 int Find(int x){24     return father[x]==x?x:father[x]=Find(father[x]);25 }26 void Union(int x,int y){27     x =Find(x);28     y =Find(y);29     if(x!=y)father[x]=y;30 }31 int main ()32 {33     int t,m;34     scanf("%d",&t);35     while(t--){36         scanf("%d%d",&n,&m);37         init();38         char ch[10];39         int x,y;40         for(int i=0;i<m;++i){41             scanf("%s%d%d",ch,&x,&y);42             int fx = Find(x);43             int fy = Find(y);44             if(ch[0]==‘A‘){45                 if(fx==fy)printf("In the same gang.\n");46                 else if(fx == Find(d[y]))printf("In different gangs.\n");47                 else printf("Not sure yet.\n");48             }49             else {50                 if(d[x]==-1){51                     d[x]=fy;52                 }53                 if(d[y]==-1){54                     d[y]=fx;55                 }56                 Union(x,d[fy]);57                 Union(y,d[fx]);58             }59         }60     }61 }