交通网络维护

题目描述

Y 同学所在的地区有 $N$ 个部落，这些部落之间由 $N-1$ 条双向道路连接，且任意两个部落之间均可以通过这些道路互相到达，即所有部落与道路构成了一棵树。

在漫长的历史中，相邻部落（即由一条道路直接相连的两个部落）之间由于资源竞争，时常会发生冲突并演变为战争。为了安全起见，当两个相邻部落处于战争状态时，连接它们的道路将变为不可通行状态。

Y 同学需要处理以下三类事件，所有事件均按时间顺序给出：

1. Q u v：询问部落 $u$ 与部落 $v$ 之间当前是否连通。若存在一条由可通行道路组成的路径连接 $u$ 和 $v$，则输出 Yes，否则输出 No。
2. C u v：部落 $u$ 与部落 $v$ 之间爆发了战争。保证 $u$ 与 $v$ 之间存在直接相连的道路，且该道路当前处于可通行状态。
3. U x：第 $x$ 次发生的战争结束了，该战争涉及的道路重新恢复为可通行状态。保证每次战争的编号与其发生的先后顺序对应（即第 $1$ 次发生的 C 操作编号为 $1$，第 $2$ 次为 $2$，以此类推），且同一场战争不会被多次结束。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别代表部落的数量和事件的总数。

接下来的 $N - 1$ 行，每行包含两个整数 $p$ 和 $q$，表示部落 $p$ 与部落 $q$ 之间存在一条初始可通行的双向道路。

接下来的 $M$ 行，每行描述一个事件，格式如下：

• Q p q：查询部落 $p, q$ 间的连通性。
• C p q：封锁部落 $p, q$ 间的道路。
• U x：撤销第 $x$ 次 C 操作导致的封锁。

输出格式

对于每个 Q 事件，输出一行一个字符串 Yes 或 No。

输入输出样例 #1

输入 #1

5 9
1 2
2 3
3 4
4 5
Q 1 4
C 2 1
C 4 3
Q 3 1
Q 1 5
U 1
U 2
C 4 3
Q 3 4

输出 #1

Yes
No
No
No

输入输出样例 #2

输入 #2

10 10
1 2
1 3
3 4
3 5
1 6
3 7
1 8
2 9
5 10
C 8 1
Q 6 1
C 2 1
Q 2 10
U 1
C 9 2
C 7 3
U 3
Q 6 7
Q 1 10

输出 #2

Yes
No
No
Yes

输入输出样例 #3

输入 #3

20 20
1 2
1 3
2 4
1 5
1 6
4 7
1 8
2 9
5 10
1 11
2 12
7 13
1 14
1 15
11 16
4 17
3 18
18 19
8 20
Q 13 5
C 14 1
C 16 11
U 1
U 2
C 20 8
Q 7 1
C 7 4
Q 17 17
Q 1 6
C 16 11
C 2 1
Q 16 2
U 3
U 5
U 6
C 2 1
C 6 1
C 13 7
C 11 1

输出 #3

Yes
Yes
Yes
Yes
No

数据范围与约定

对于 $100\%$ 的数据，保证 $1 \le N, M \le 3 \times 10^5$，$1 \le u, v \le N$。

特殊性质 A：保证给定的树是一条链，即部落 $i$ 与部落 $i+1$ 之间存在道路（$1 \le i < N$）。 特殊性质 B：保证输入的事件中不存在 U 操作。