学步园

/*将敌人和朋友并到一个集合中，用另外一个数组（rel[i]）存放i和集合代表元素（就是ji[i]中存的）的关系。
如果两个元素不在统一集合内，说明他们关系不清楚；
如果两个元素在同一个集合内：
							1.他们和集合代表元素的关系相同，他们则是朋友
							2.不同就是敌人*/
#include<stdio.h>
int ji[100010],rel[100010];//ji[]存放集合代表元素,re;[i]存放i和集合代表元素的关系
int root(int x)
{
	int t;
	if(x==ji[x])
		return x;
	t=ji[x];
	ji[x]=root(ji[x]);
	rel[x]=(rel[t]+rel[x])%2;//更新和集合代表元素的关系
	return ji[x];
}
int main()
{
	int t,n,m,i;
	char o;
	int x,y,fx,fy;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(i=0;i<=n;i++)
		{
			ji[i]=i;
			rel[i]=0;
		}
		if(n==2)
		{
			ji[2]=1;
			rel[2]=1;
		}
		for(i=1;i<=m;i++)
		{
			getchar();
			scanf("%c %d%d",&o,&x,&y);
			fx=root(x);
			fy=root(y);
			if(o=='A')
			{
				if(fx==fy)
				{
					if(rel[x]==rel[y])
						printf("In the same gang.\n");
					else printf("In different gangs.\n");
				}
				else printf("Not sure yet.\n");
			}
			else
			{
				if(fx<fy)
				{
					ji[fy]=fx;
					rel[fy]=!((rel[x]+rel[y])%2);
				}
				else
				{
					ji[fx]=fy;
					rel[fx]=!((rel[x]+rel[y])%2);
				}
			}
		}
	}
	return 0;
}