Description

约翰和贝西在玩叠积木，每块积木是大小一样的立方体，将几块积木叠在一起可以得到更高的长方体。积木是有磁性的，叠起来的积木分不开。

约翰负责把积木叠高，而贝西负责清点积木的高度。一开始共有 N 块积木，编号为 1 到 N，所有积木都是分开的，没有积木叠在一起。

每次移动积木的时候，约翰会先选择一块积木 X，再选择另一块积木 Y ，把 X 搬到 Y 的上方。

如果 X 已经和其它积木叠在一起了，那么应将这叠积木整体移动到 Y 的上方；如果 Y 已经和其它积木叠在一起了的，假设在 Y 上方最高处的积木为 Z，那么应将 X 所在的那叠积木移动到 Z 的上方。

在约翰辛苦劳动的同时，贝西在一边计算积木已经叠得多高了。约翰和贝西是交替工作的，可惜贝西不太擅长于数数，请你帮她计算一下，在一些时刻，指定的积木的下方还有多少其他积木。

Input Format

• 第一行：两个整数 N 和 Q， 1 ≤ N ≤ 30000; 1 ≤ Q ≤ 100000

• 第二行到 Q + 1 行：每行描述一个事件，表示约翰的一个移动操作，或贝西的一个查询，首先有一个大写字母：

– 如果字母是 M，随后会有两个整数 X 和 Y ，约翰把积木 X 移动到 Y 的上方， 1 ≤ X; Y ≤N，保证移动之前 X 和 Y 不会在同一堆积木里；

– 如果字母是 C，随后有一个整数 T，表示贝西想知道在积木 T 的下方还有多少其它积木，1 ≤ T ≤ N

Output Format

• 对每个来自贝西的查询，输出正确答案，用换行符分隔

6 6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4

1
0
2

Hint

解释 第一次查询时， 1 下只有一个 6；第二次查询时， 3 下没有任何积木；第三次查询时， 4 下有两块积木： 1 和 6

Source

3.4.4并查集