题目描述 Description
经过不懈的努力，Hzwer召唤了很多陨石。已知Hzwer的地图上共有n个区域，且一开始的时候第i个陨石掉在了第i个区域。有电力喷射背包的ndsf很自豪，他认为搬陨石很容易，所以他将一些区域的陨石全搬到了另外一些区域。
在ndsf愉快的搬运过程中，Hzwer想知道一些陨石的信息。对于Hzwer询问的每个陨石i，你必须告诉他，在当前这个时候，i号陨石在所在区域x、x区域共有的陨石数y、以及i号陨石被搬运的次数z。
输入描述 Input Description
输入的第一行是一个正整数T。表示有多少组输入数据。
接下来共有T组数据，对于每组数据，第一行包含两个整数：N和Q。
接下来Q行，每行表示一次搬运或一次询问，格式如下：
T A B：表示搬运，即将所有在A号球所在地区的陨石都搬到B号球所在地区去。
Q A：悟空想知道Ａ号陨石的x，y，z。
输出描述 Output Description
对于第ｉ组数据，第一行输出“Case i：”接下来输出每一个询问操作的x，y，z，每一个询问操作的答案占一行。每组数据之间没有空行。
样例输入 Sample Input
2
3 3
T 1 2
T 3 2
Q 2
3 4
T 1 2
Q 1
T 1 3
Q 1
样例输出 Sample Output
Case 1：
2 3 0
Case 2：
2 2 1
3 3 2
数据范围及提示 Data Size & Hint
20%的数据保证：0≤T≤20，2＜N＜＝100，2＜Q＜＝100。
100%的数据保证：0≤T≤100，2＜N＜＝10000，2＜Q＜＝10000。
对于所有数据保证搬运操作中AB在Ｎ的范围内且所在区域不相同。
/*
带权并查集，思路同”银河英雄传说“那道题
*/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int T,n,m,a,b,ra;
int f[],sz[],d[];
char cmd;
int read(){
char ch=getchar();
int f=,x=;
while(!(ch>=''&&ch<='')){if(ch=='-')f=-;ch=getchar();};
while(ch>=''&&ch<=''){x=x*+(ch-'');ch=getchar();};
return x*f;
}
int findf(int x){
if(x != f[x]){
int r = findf(f[x]);
d[x] += d[f[x]];
f[x] = r;
}
return f[x];
}
int main(){
T = read();
int cse = ;
while(cse <= T){
printf("Case %d:\n",cse);
n = read();
m = read();
for(int i = ;i <= n;i++){
f[i] = i;
sz[i] = ;
d[i] = ;
}
for(int i = ;i <= m;i++){
scanf("%c",&cmd);
while(cmd != 'T' && cmd != 'Q') scanf("%c",&cmd);
if(cmd == 'T'){
a = read();
b = read();
a = findf(a);
b = findf(b);
f[a] = b;
sz[b] += sz[a];
d[a]++;
}else{
a = read();
ra = findf(a);
printf("%d %d %d\n",ra,sz[ra],d[a]);
}
}
cse++;
}
return ;
}