题目描述

若某个家族人员过于庞大，要判断两个人是否是亲戚确实不容易。现在给出亲戚关系图，需实现以下功能：

• 处理两种操作，一种是合并两人所在家族（因亲戚关系具有传递性，若 x 和 y 是亲戚，y 和 z 是亲戚，那么 x 和 z 也是亲戚，且 x 的亲戚与 y 的亲戚会融合为同一大家庭）；
• 另一种是查询某个人所在家族的总人数。

输入格式

第一行输入两个整数 n 和 m（n ≤ 100,000，m ≤ 200,000 ），分别表示总人数和操作信息的数量。
接下来 m 行，每行是以下两种格式之一：

• M a b：表示 a 和 b 具有亲戚关系，需将两人所在家族合并。
• Q a：要求输出 a 所在家族的总人数。

输出格式

对于每个 Q a 操作，输出一行整数，表示 a 所在家族的总人数。

样例输入

5 10
M 3 2
Q 4
M 1 2
Q 4
M 3 2
Q 1
M 3 1
Q 5
M 4 2
Q 4

样例输出

1
1
3
1
4

数据范围

• 人数 n 范围：1 ≤ n ≤ 100,000
• 操作数 m 范围：1 ≤ m ≤ 200,000