两个团伙

题目：

有n个人分别属于两个团伙，从1到n编号，接下来m组形如 ch x y的数据，ch为“D"表示 x, y属于不同的团伙，ch为"A"表示询问x，y是否属于同一个团伙。

输入

输入一个整数

对于每一组数据。

第一行给出两个整数， $10^5), m(1 le m le 10^5)n(1≤n ≤105),m(1≤m≤105)。接下来m行，每行形如ch x y。$

输出

对于A x y的询问操作，如果x,y属于同一团伙输出 "In the same gang."；如果属于不同团伙，输出 "In different gangs." ；如果不确定，输出 "Not sure yet."。

样例

输入

输出

Not sure yet.
In different gangs.
In the same gang.

/*************************************************************************
> Author: Henry Chen
> Mail: 390989083@qq.com
> Created Time: 日 8/23 21:25:56 2020
************************************************************************/

#include<bits/stdc++.h>
using namespace std;
int fa[100009],sm[100009],sn[100009];
int find(int x)
{
if(fa[x] == x) return x;
int k = find(fa[x]);
sm[x] += sm[fa[x]];
fa[x] = k;
return fa[x];
}
void work()
{
int n,m;
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
fa[i] = i;
sm[i] = 0;
sn[i] = 0;
}
while(m--)
{
char c;
scanf("%*c%c",&c);
int x,y;
scanf("%d%d",&x,&y);
if(c == 'A')
{
if(find(x) != find(y)) puts("Not sure yet.");
else if((sm[x]+sm[y])%2 == 0) puts("In the same gang.");
else puts("In different gangs.");
}
else
{
if(find(x) != find(y))
{
int fx = find(x);
int fy = find(y);
if(sn[fx] > sn[fy])
{
fa[fy] = fx;
sm[fy] = (sm[x]+sm[y]+1)%2;

}
else
{
fa[fx] = fy;
sm[fx] = (sm[x]+sm[y]+1)%2;
if(sn[fx] == sn[fy])
{
sn[fx]++;
}
}
}
}
}
}
int main()
{
int t;
cin >> t;
while(t--)
{
work();
}
return 0;
}