题目大意：有两个帮派，命令D a b表示a,b两人不在同一个帮派里，动态询问两个人是不是在同一个帮派。

并查集。d[x]=0 or 1 表示x是否与根节点在同一帮派。碰到D a b 就合并，同时d[fa]:=(d[a]+d[b]+1) mod 2.

路径压缩的时候维护一下就好了，方法如下。

1 function find(x:longint):longint;2   var fa:longint;3   begin4     fa:=f[x];5     if f[x]=0 then exit(x);6     f[x]:=find(f[x]);7     d[x]:=(d[x]+d[fa])mod 2;8     exit(f[x]);9   end;

code：

1 var 2   f,d:Array[1..100000]of longint; 3   tt,ttt,i,p,q,a,b,n,m:longint; 4   c,space:char; 5 function find(x:longint):longint; 6   var fa:longint; 7   begin 8     fa:=f[x]; 9     if f[x]=0 then exit(x);10     f[x]:=find(f[x]);11     d[x]:=(d[x]+d[fa])mod 2;12     exit(f[x]);13   end;14 15 begin16 readln(tt);17 for ttt:=1 to tt do18   begin19   fillchar(f,sizeof(f),0);20   fillchar(d,sizeof(d),0);21   readln(n,m);22   for i:=1 to m do23     begin24     readln(c,space,a,b);25     if c='A' then26       begin27       p:=find(a);28       q:=find(b);29       if p<>q then writeln('Not sure yet.')30       else31         if d[a]<>d[b] then writeln('In different gangs.')32         else writeln('In the same gang.');33       end;34     if c='D' then35       begin36       p:=find(a);37       q:=find(b);38       if p<>q then39         begin40         f[p]:=q;41         d[p]:=(d[a]+d[b]+1) mod 2;42         end;43       end;44     end;45     end;46 end.