学步园

/*

分析注意几点：
1，龙珠不可能 再次回到他最初呆的城市
2，压缩路径，转移的次数为 **原始 + 前一个父亲节点的转移次数 ** 

*/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
using namespace std;
#define manx 10009
int pre[manx],ans[manx],sum[manx];

int root(int x){
    if(pre[x]==x) return x;
    int temp = pre[x];
    pre[x] = root(pre[x]);
    ans[x] += ans[temp];
    return pre[x];  
}

int main(){
    int t;
    scanf("%d",&t);
    for(int ca=1;ca<=t;ca++){
        int n,q;
        scanf("%d%d",&n,&q);
        printf("Case %d:\n",ca);  
        for(int i=0;i<=n;i++){
            pre[i]=i;
            ans[i]=0;
            sum[i]=1;
        }
        char a[2];
        int b,c;
        for(int i=1;i<=q;i++){
            scanf("%s",a);
            if(a[0]=='T'){
                scanf("%d%d",&b,&c);
                b = root(b);
                c = root(c);
                if(b!=c){
                    pre[b] = c;
                    sum[c] += sum[b];//城市里龙珠的总数 
                    ans[b]++;
                }
            }
            if(a[0]=='Q'){
                scanf("%d",&b);//某个龙珠 
                int P = root(b);
                printf("%d %d %d\n",P,sum[P],ans[b]);
            }
        }
    }
}