Background

{{In a world called Travian live many tribes both large and small. The strongest among them are the Romans, Gauls, and Germans. They have fought countless battles over resources and land. Many famous heroes were born during these times, and many moving stories were left behind.

Between the many tribes, there are roads connecting them. For simplicity, you can regard the road network between tribes as a tree, which shows how important each road is in the Travian world. With these roads, builders can travel for friendly diplomacy.

However, things are not always so pleasant. Due to a lack of resources, neighboring tribes (connected by one road) often have conflicts, and sometimes these escalate into large-scale wars between tribes.

To avoid collateral damage, whenever two neighboring tribes are at large-scale war, the road between them is closed to traffic. Some powerful tribes can even go to war with multiple neighboring tribes at the same time; the roads within these war zones are dangerous and impassable.

As the saying goes, after long division comes union. After a hard battle, two tribes may sign a truce agreement (a temporary ceasefire; they may go to war again later). Then the road between them becomes passable again, and builders can pass through to buy the latest Town Hall blueprints to strengthen their tribes.

For simplicity, we number all war events in the order they start (the earliest war is numbered $1$, the second $2$, and so on). When two tribes make a truce, you will be told the number of that war. That war is then recorded in history and no longer exists. Of course, this does not affect the numbering of other wars.

Builders hate wars. Because of wars, a builder traveling from one tribe to another for friendly exchange may make a wasted trip. So before they set out, they will ask you whether they can reach their destination.}}

Problem 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