题目描述

题目译自 BalticOI 2021 Day1「Inside information」，译者 Shuchong。

有 $N$ 个服务器，第 $i$ 个服务器存储着第 $i$ 块数据，现在有若干种操作：

• S a b 第 $a$ 个服务器与第 $b$ 个服务器共享数据，即这两个服务器同时拥有这两个服务器本身拥有的数据块的和，并自动去重（可以理解为数据块之并）。
• Q a d 查询第 $a$ 个服务器是否拥有第 $d$ 块数据。
• C a 查询存储数据块 $a$ 的服务器数量。

S 操作有 $N-1$ 次，如果把共享看做连边，那么最后将形成以 $N$ 个服务器为点的一棵树；Q 操作和 C 操作一共有 $K$ 次。

求对于每个 Q 操作和 C 操作返回的结果。

输入格式

第一行两个整数 $N,K$ 代表服务器个数和操作个数。

接下来 $N+K-1$ 行每行代表一个操作。

输出格式

共有 $K$ 行：

• 对于 Q 操作，输出 yes 或 no 代表是否拥有第 $d$ 块数据；
• 对于 C 操作，输出一个整数代表服务器数量。

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

数据范围与提示

对于 $100\%$ 的数据，$1 \le N,K \le 1.2 \times 10^5$。

• Subtask 1（5 pts）：$N \le 4\times 10^3$。
• Subtask 2（5 pts）：第 $1$ 个服务器与第 $2,3,\cdots,N$ 个服务器共享数据。
• Subtask 3（10 pts）：如果 $|A-B|=1$，那么第 $A$ 个服务器和第 $B$ 个服务器共享数据。
• Subtask 4（20 pts）：如果 $A<B$ 且 $2\times A=B$ 或 $2\times A+1=B$，那么第 $A$ 个服务器和第 $B$ 个服务器共享数据。
• Subtask 5（25 pts）：每个服务器最多与 $5$ 个服务器共享数据。
• Subtask 6（35 pts）：无特殊限制。

在本题，如果你能解决一个子任务下所有从不询问查询第 $a$ 个服务器拥有的数据块数量的测试点（即数据没有以 C 开头的行），你将获得这个子任务 $50\%$ 的分数。在 LibreOJ，测试时会将一个子任务拆为两个子任务进行测试，测评时子任务 $2i-1$ 和 $2i$ 对应的是题目中的 Subtask $i$。