Relatives 2

Problem Background

Special for beginners, ^_^

Problem Description

If a family is too large, it is indeed not easy to tell whether two people are relatives. Now given a certain relatives graph, find the number of people in the family of any given person.

The rule is: if $x$ and $y$ are relatives, and $y$ and $z$ are relatives, then $x$ and $z$ are also relatives. If $x, y$ are relatives, then all of $x$'s relatives are also $y$'s relatives, and all of $y$'s relatives are also $x$'s relatives.

Input Format

The first line: three integers $n$ ($n \le 100,000$, $m \le 200,000$), representing $n$ people and $m$ pieces of information.

The following $m$ lines: each piece of information is in one of two forms:

• M a b: means $a$ and $b$ are relatives.
• Q a: requires outputting the number of people in the family of $a$.

Output Format

Output the number of people in the family of $a$.

Sample Input

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

Sample Output

1
1
3
1
4

Constraints

Time limit: 1s; memory limit: 1024 KiB for each test case.