登录/注册
349. 城市帮派 Find them, Catch them(挑战程序设计竞赛)
时间限制: C/C++ 1000 ms | 其他语言 2000 ms
内存限制: C/C++ 64 MB | 其他语言 128 MB
尝试次数: 42 | 通过次数: 20
尝试人数: 7 | 通过人数: 7
标签: 并查集
难度: 中等
0
0

一个城市里有两个帮派,另外有 NN 个成员,成员从 1N1 \sim N 进行编号,每个成员来自于其中一个帮派。

给定 MM 个信息,每个信息有两种格式:

  • D a bD \ a \ ba,b(1a,bN,ab)a,b(1 \leq a,b \leq N, a \neq b) 两个人不是一个帮派的
  • A a bA \ a \ b: 判断 a,b(1a,bN,ab)a,b(1 \leq a,b \leq N, a \neq b) 两个人是否为同一个帮派
    • 两人同属一个帮派则输出 In the same gang.
    • 不同属一个帮派则输出 In different gangs.
    • 根据现有的消息无法确定则输出 Not sure yet.

输入

  • 第一行整数 T(1T20)T(1 \leq T \leq 20),表示有多少组测试数据
  • 每组测试数据格式如下:
    • 第一行两个整数 N,M(1N,M105)N,M(1 \leq N,M \leq 10^5),表示成员的数量,消息的数量
    • 接下来 MM 行,每行一条消息,随机给出,格式如上所述

输出

  • 对于每个 AA 操作,需要一行结果,可能为 In the same gang.In different gangs.Not sure yet.
样例 1
输入
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.