1837. 小强的烦恼

单点时限: 2.0 sec

内存限制: 256 MB

小强生日到了,他的朋友旺才都来参加他的生日了,而且都来了,超级的多,有 $n$ $(n \leq 10^5)$ 个旺才,这么多的旺才,必然会出现很多矛盾,使得这些旺才分为很多团伙,现在给你 $m$ $(m \leq 10^5)$ 条信息,让你来对每条信息做处理,一共有 2 种信息:

  1. A x y,就是添加一条信息旺才 x 和旺才 y 是敌对的团伙。数据保证不会是 x y 已经是同一团伙的情况。
  2. Q x y,询问旺才 x 和旺才 y 之间的关系,有三种关系:
    • 属于同一团伙。
    • 属于敌对的团伙。
    • 两者之间的关系不确定。

输入格式

首先输入一个 $T$ $(T \leq 20)$,代表有多少个 case,接下来对于每个 case,首先是 2 个数 $n,m$,$n$ 是小强家旺才的个数,编号从 $1$ 到 $n$,接下来 $m$ 行,每行一个信息,每条信息由 2 种格式,如上面的描述。

输出格式

A x y,不要求输出内容,只对 Q x y,将 x y 之间的关系输出,输出内容:

  • 属于同一团伙,输出 In the same gang.
  • 属于敌对的团伙 In different gangs.
  • 两者之间的关系不确定 Not sure yet.

具体参照 Sample。

样例

Input
1
6 9
Q 1 2
A 1 2
Q 1 2
A 3 4
Q 1 3
A 5 6
A 4 5
Q 3 6
Q 4 6
Output
Not sure yet.
In different gangs.
Not sure yet.
In different gangs.
In the same gang.

提示

敌人的敌人是朋友。

106 人解决,150 人已尝试。

226 份提交通过,共有 728 份提交。

3.7 EMB 奖励。

创建: 12 年,7 月前.

修改: 2 年,10 月前.

最后提交: 2 天,9 小时前.

来源: N/A

题目标签
dsu