Description

There are $N$ servers. The $i$-th server stores the $i$-th data block at the beginning. Now there are several types of operations:

• S a b: Server $a$ and server $b$ share data. That is, after the operation, both servers will contain the union of the data blocks originally held by these two servers, with duplicates removed (you can think of it as the union of data blocks).
• Q a d: Query whether server $a$ has data block $d$.
• C a: Query the number of servers that store data block $a$.

There are exactly $N-1$ S operations. If we treat each share as adding an edge, in the end these edges form a tree with the $N$ servers as nodes. In total, there are $K$ operations of type Q and C.

For each Q operation and C operation, output the corresponding result.

Input Format

The first line contains two integers $N, K$, representing the number of servers and the number of query operations.

The next $N+K-1$ lines each describe one operation.

Output Format

Output $K$ lines:

• For a Q operation, output yes or no to indicate whether it has data block $d$.
• For a C operation, output one integer representing the number of servers.

6 9
S 1 2
S 1 3
S 3 4
Q 5 1
S 4 5
S 1 6
Q 5 1
Q 1 5
C 1
C 2
C 3
C 4
C 5
C 6

no
yes
no
6
6
5
3
2
2

4 4
S 1 2
S 1 3
S 3 4
Q 2 1
Q 2 2
Q 2 3
Q 2 4

yes
yes
no
no

Hint

Constraints

This problem uses bundled testdata.

• Subtask 1 (5 pts): $N \le 4000$.
• Subtask 2 (5 pts): Server $1$ shares data with servers $2, 3, \cdots, N$.
• Subtask 3 (10 pts): If $|A-B|=1$, then server $A$ shares data with server $B$.
• Subtask 4 (20 pts): If $A<B$ and $2A=B$ or $2A+1=B$, then server $A$ shares data with server $B$.
• Subtask 5 (25 pts): Each server shares data with at most $5$ servers.
• Subtask 6 (35 pts): No special restrictions.

For $100\%$ of the testdata, $1 \le N, K \le 1.2 \times 10^5$.

Notes

Translated from BalticOI 2021 Day1 B Inside information。

Translated by ChatGPT 5