题目描述：

经过不懈的努力，Hzwer召唤了很多陨石。已知Hzwer的地图上共有n个区域，且一开始的时候第i个陨石掉在了第i个区域。有电力喷射背包的ndsf很自豪，他认为搬陨石很容易，所以他将一些区域的陨石全搬到了另外一些区域。

在ndsf愉快的搬运过程中，Hzwer想知道一些陨石的信息。对于Hzwer询问的每个陨石i，你必须告诉他，在当前这个时候，i号陨石在所在区域x、x区域共有的陨石数y、以及i号陨石被搬运的次数z。

输入描述：

输入的第一行是一个正整数T。表示有多少组输入数据。

接下来共有T组数据，对于每组数据，第一行包含两个整数：N和Q。

接下来Q行，每行表示一次搬运或一次询问，格式如下：

T A B：表示搬运，即将所有在A号球所在地区的陨石都搬到B号球所在地区去。

Q A：悟空想知道Ａ号陨石的x，y，z。

输出描述：

对于第ｉ组数据，第一行输出“Case i：”接下来输出每一个询问操作的x，y，z，每一个询问操作的答案占一行。每组数据之间没有空行。

样例输入：

2

3 3

T 1 2

T 3 2

Q 2

3 4

T 1 2

Q 1

T 1 3

Q 1

样例输出：

Case 1：

2 3 0

Case 2：

2 2 1

3 3 2

数据范围：

20%的数据保证：0≤T≤20，2＜N＜＝100，2＜Q＜＝100。

100%的数据保证：0≤T≤100，2＜N＜＝10000，2＜Q＜＝10000。

对于所有数据保证搬运操作中AB在Ｎ的范围内且所在区域不相同。

题解

带权并查集。。。

移动次数标记在每个集合的根

压缩路径时，每个点先获得它父亲的移动次数，再换父亲