题目描述

塔杜市警察局决定结束混乱，采取行动铲除市内的两大帮派——龙帮和蛇帮。然而，警方首先需要确定罪犯所属的帮派。当前的问题是，给定两名罪犯，他们是否属于同一个帮派？你必须根据不完整的信息做出判断。（因为黑帮成员总是秘密行动。）

假设塔杜市目前有$N$（$N \leq 10^5$）名罪犯，编号从$1$到$N$。当然，至少有一人属于龙帮，同样至少有一人属于蛇帮。你将按顺序获得$M$（$M \leq 10^5$）条信息，这些信息分为以下两种类型：

$1$. $D [a] [b]$

其中$[a]$和$[b]$是两名罪犯的编号，他们属于不同的帮派。

$2$. $A [a] [b]$

其中$[a]$和$[b]$是两名罪犯的编号。你需要判断$a$和$b$是否属于同一个帮派。

输入

输入的第一行包含一个整数$T$（$1 \leq T \leq 20$），表示测试用例的数量。接下来是$T$个测试用例。每个测试用例以两个整数$N$和$M$开始，随后是$M$行，每行包含一条上述信息。

输出

对于每个测试用例中的每条"$A [a] [b]$"信息，你的程序应根据之前获得的信息给出判断。答案可能是"$In$ $the$ $same$ $gang.$"、"$In$ $different$ g$angs.$"或"$Not$ $sure$ $yet.$"。

输入数据 1

1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4

输出数据 1

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

来源

POJ 月赛 -- 2004.07.18