发现它，抓住它 一个城市中有两个犯罪团伙A和B，你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为，警察所获得的信息是有限的。假设现在有N起案件(N<=100000)，编号为1到N，每起案件由团伙A或团伙B所为。你将按时间顺序获得M条信息(M<=100000)，这些信息分为两类： D [a] [b] 其中[a]和[b]表示两起案件的编号，这条信息表明它们属于不同的团伙所为 A [a] [b] 其中[a]和[b]表示两起案件的编号，这条信息需要你回答[a]和[b]是否是同一个团伙所为 注意你获得信息的时间是有先后顺序的，在回答的时候只能根据已经接收到的信息做出判断。 时间限制：1000 内存限制：65536 输入 第一行是测试数据的数量T(1<=T<=20)。 每组测试数据的第一行包括两个数N和M，分别表示案件的数量和信息的数量，其后M行表示按时间顺序收到的M条信息。 输出 对于每条需要回答的信息，你需要输出一行答案。如果是同一个团伙所为，回答"In the same gang.“，如果不是，回答"In different gangs.”，如果不确定，回答”Not sure yet."。 样例输入 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.
正确答案：参考程序（C++）：带权并查集（种类并查集）。开2N空间，D a b表示不同团伙：union(a,b+N)与union(a+N,b)；A查询判断是否同根。核心：对立关系并查集。
试卷来源：202209 青少年等级考试C/C++真题八级