1 /*
 2 Author:    Leo.W
 3 Descriptipn:  龍珠在哪里，那里有多少龍珠，目標龍珠移動了多少次。移動龍珠，并將在一起的龍珠同時移動。
 4 How to Do:  T A B即將Ath龍珠所在地所有龍珠移動到Bth龍珠所在地
 5             Q A顯示Ath龍珠所在地ID及此地的龍珠數(shù)和Ath龍珠的移動次數(shù)  
 6   */
 7 #include <cstdio>
 8 #include <cstdlib>
 9 #define MAXSIZE 200001
10 int n,q;
11 struct ball{
12     int id;//所在城市編號
13     int par;//同在一座城市的上一節(jié)點
14     int trans;//該龍珠的移動次數(shù)
15 }lz[MAXSIZE];
16 int counts[MAXSIZE];//某城市的龍珠數(shù)目
17 char ch;
18 
19 int findSet(int x){
20     int t=lz[x].par;
21     if(lz[x].par!=x)
22         lz[x].par=findSet(lz[x].par);
23     lz[x].trans+=lz[t].trans;
24     return lz[x].par;
25 }
26 inline void merge(int x,int y){//從xth所在城市到y(tǒng)th所在城市
27     int px=findSet(x);
28     int py=findSet(y);
29     if(px==py)    return;
30     counts[lz[py].id]+=counts[lz[px].id];
31     counts[lz[px].id]=0;
32     lz[px].id=lz[py].id;
33     lz[px].par=py;
34     lz[px].trans++;
35 }
36 inline void makeSet(int n){
37     int i;
38     for(i=1;i<=n;i++)//從1到n
39         lz[i].id=i,lz[i].par=i,lz[i].trans=0,counts[i]=1;
40 }
41 inline void scan(int &x){
42     while (ch=getchar(),ch<'0'||ch>'9');x=ch-'0';
43     while (ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-'0';
44 }
45 int main(){
46     freopen("in.txt","r",stdin);
47     int t,no=1;
48     scan(t);
49     while (t--){
50         printf("Case %d:\n",no++);
51         scan(n);
52         scan(q);
53         makeSet(n);
54         while (q--){
55             char s;    int a,b;
56             while (s=getchar(),s<'A'||s>'Z');
57             scan(a);
58             if (s=='T'){
59                 scan(b);
60                 merge(a,b);    
61                 continue;
62             }
63             int tt=findSet(a);
64             printf("%d %d %d\n",lz[tt].id,counts[lz[tt].id],lz[a].trans);            
65         }
66     }
67     return 0;
68 }
69 
70