题目链接：

塔都市的警察局决定以混乱为目标，作为启动行动，扎根城市中的两个帮派，Gang Dragon和Gang Snake。

但是，警方首先需要确定犯罪分子属于哪个团伙。目前的问题是，两名罪犯; 他们属于同一个氏族吗？

您必须根据不完整的信息做出判断。（因为歹徒总是暗中行动。）

假设N（N <= 10 ^ 5）罪犯目前在塔都市，编号从1到N.当然，他们中至少有一人属于Gang Dragon，

同样为Gang Snake。您将按顺序给出M（M <= 10 ^ 5）个消息，它们分为以下两种：

1。D [a] [b]

其中[a]和[b]是两个罪犯的数字，以及他们属于不同的帮派。

2. A [a] [b]

其中[a]和[b]是两个罪犯的数量。这需要您决定a和b是否属于同一个团伙。

输入

输入的第一行包含单个整数T（1 <= T <= 20），即测试用例的数量。然后是T案例。

每个测试用例以具有两个整数N和M的行开始，接着是M行，每行包含如上所述的一个消息。

产量

对于每种情况下的每条消息“A [a] [b]”，您的程序应根据之前获得的信息进行判断。

样本输入

1

5 5

A 1 2

D 1 2

A 1 2

D 2 4

A 1 4

样本输出

Not sure yet.

In different gangs.

In the same gang.

这个题目也是典型的并查集的题目,因为总共只有两个黑帮，所以可以用两个集合来求解。当让，用一个集合也可以。

只是要对relation进行细心设置(可以设置relatiin：0表示关系相同，1为关系不同)。在对一个元素执行Find（）操作时，如果它与父亲结点realtion相同，父亲结点与根结点relation相同，那么该元素与根结点关系也相同。否则是不同的。

1 int DisJoinSet ::Find(int x) 2 { 3     int temp = tree[x].parent;//temp x的父亲结点 4     if(x != tree[x].parent) 5     { 6         tree[x].parent = Find(tree[x].parent);//递归在双亲中找x 7     // tree[temp].relation必为temp结点（x的父节点）与根节点的关系，tree[x].relation最初为x与temp的关系， 8     // tree[x].relation == tree[temp].relation意味着tree[x].relation和tree[temp].relation同为1，或者同为0 9     // 如果tree[x].relation和tree[temp].relation同为1，意味着根节点与temp不同类，temp与x不同类，总共只有2个集合，x与根节点必定同类。10     // 如果tree[x].relation和tree[temp].relation同为0，意味着根节点与temp同类，temp与x同类，x与根节点也必定同类。11         if(tree[x].relation == tree[temp].relation)12         {13             tree[x].relation = 0;14         }15     // tree[x].relation != tree[temp].relation意味着tree[x].relation和tree[temp].relation一个为1，一个为0，16     // 如果tree[temp].relation为false，tree[temp].relation为1，意味着根节点和temp同类，temp与x不同类，那么x与根节点必然不同类17     // 如果tree[temp].relation为true，tree[x].relation为0，意味着根节点和temp不同类，temp与x同类，那么x与根节点必然不同类18         else19         {20             tree[x].relation = 1;21         }    22         return tree[x].parent;// 返回根节点下标23     }24     else25     {26         return x;27     }28 }

在进行合并操作时，因为合并的x和y是属于不同集合的，所以和上面一样的推理。

1 void DisJoinSet ::Union(int x,int y) 2 { 3     int rootx = Find(x); 4     int rooty = Find(y); 5     if(rootx == rooty) 6     { 7         return ; 8     } 9     if(tree[rootx].rank > tree[rooty].rank)10     {11         tree[rooty].parent = rootx;12         // 此时rooty与其根结点rootx的关系如何确定？因为Find方法也在进行路径压缩，x的父节点是rootx，y的父节点的rooty13         // 如果tree[x].relation和tree[y].relation均为1，说明x和rootx不同类，y和rooty不同类，而已知x和y不同类，因此rooty和rootx不同类；14         // 如果tree[x].relation和tree[y].relation均为0，说明x和rootx同类，y和rooty同类，而已知x和y不同类，因此rooty和rootx不同类15         if(tree[x].relation == tree[y].relation)16         {17             tree[rooty].relation = 1;18         }19         // 如果tree[x].relation为1，tree[y].relation为0，说明x和rootx不同类，y和rooty同类，而已知x和y不同类，因此rooty和rootx必同类；20         // 如果tree[x].relation为0，tree[y].relation为1，说明x和rootx同类，y和rooty不同类，而已知x和y不同类，因此rooty和rootx必同类；21         else22         {23             tree[rooty].relation = 0;24         }25     }26     else27     {28         tree[rootx].parent = rooty;29         if(tree[rootx].rank == tree[rooty].rank)30         {31             tree[rooty].rank ++;32         }33         // 此时rooty与其根结点rootx的关系如何确定？因为Find方法也在进行路径压缩，x的父节点是rootx，y的父节点的rooty34         // 如果relation[x]和relation[y]均为true，说明x和rootx不同类，y和rooty不同类，而已知x和y不同类，因此rooty和rootx不同类；35         // 如果relation[x]和relation[y]均为false，说明x和rootx同类，y和rooty同类，而已知x和y不同类，因此rooty和rootx不同类36         if(tree[x].relation == tree[y].relation)37         {38             tree[rootx].relation = 1;39         }40         // 如果tree[x].relation为1，tree[y].relation为0，说明x和rootx不同类，y和rooty同类，而已知x和y不同类，因此rooty和rootx必同类；41         // 如果tree[x].relation为0，tree[y].relation为1，说明x和rootx同类，y和rooty不同类，而已知x和y不同类，因此rooty和rootx必同类；42         else43         {44             tree[rootx].relation = 0;45         }46     }47 }

完整代码：

1 #include
          
             2 #include
           
              3 #include
            
               4 #include
             
                5 #include
              
                 6 #include
               
                 7 #include