问题 J: 进阶1.1.4 帮派
内存限制：128 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：206
解决：50
题目描述
市里一共有两个黑帮，青龙帮和白蛇帮。警察必须根据不完整的信息做出判断，判断两名罪犯是否属于同帮派。
假设有N(2≤N≤105) 个罪犯，编号为1~N，已知其中至少有一人属于青龙帮，一人属于白蛇帮。
警察局共收集到了M (M≤105)个消息，消息类型有两种:
假设有N(2≤N≤105) 个罪犯，编号为1~N，已知其中至少有一人属于青龙帮，一人属于白蛇帮。
警察局共收集到了M (M≤105)个消息，消息类型有两种:
- D a b，表示a和b属于不同的帮派；
- A a b，表示查询a和b是否属于同一帮派。
输入
第1行包含单个整数T (1≤T≤20)，表示测试用例的数量；
每个测试用例以两个整数N(2≤N≤105) 和M(≤105) 开头； 接着M行，每行包含如上所述的一个消息。
每个测试用例以两个整数N(2≤N≤105) 和M(≤105) 开头； 接着M行，每行包含如上所述的一个消息。
输出
对每一个查询操作“A”，都根据之前获得的信息进行判断，单行输出可能的答案：
- 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.