Description

{{You need to handle the three types of events below. All events are given in chronological order. Initially, all roads are passable (no wars).

1. Q p q A builder starting from the $p$-th tribe wants to know whether they can reach the $q$-th tribe. You must answer Yes / No. Note the capitalization.

2. C p q The $p$-th tribe and the $q$-th tribe go to war. It is guaranteed they are adjacent tribes and are currently in a truce (not at war). The road between them becomes impassable.

3. U x The $x$-th war ends and is recorded in history; it no longer exists (this message will not be given multiple times). The corresponding road becomes passable again.}}

Input Format

{{The first line contains two integers $n$ and $m$: $n$ is the number of tribes, and $m$ is the total number of events.

The next $n - 1$ lines each contain two integers $p, q$, indicating there is a road connecting the $p$-th tribe and the $q$-th tribe.

The next $m$ lines each describe one event, as detailed in the Description.}}

Output Format

{{For each query, output one Yes or No on its own line, indicating whether a builder starting from the $p$-th tribe can reach the $q$-th tribe.}}

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

Yes
No
No
No

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

Yes
No
No
Yes

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

Yes
Yes
Yes
Yes
No

Hint

{{For $30\%$ of the testdata, $n, m \leq 6 \times 10^3$.

For another $30\%$ of the testdata, the tribes form a chain, and there is a road between $i$ and $i + 1$.

For another $30\%$ of the testdata, $n, m \leq 10^5$.

For $100\%$ of the testdata, $1 \leq n, m \leq 3 \times 10^5$.}}

Translated by ChatGPT 5