Description

In 2016, Jiayuan jiejie had just learned about trees and was very happy. Now she wants to solve the following problem: given a rooted tree with root $1$, there are two types of operations:

1. Mark operation: put a mark on some node. (At the very beginning, only node $1$ is marked, and all other nodes are unmarked. You may mark the same node multiple times.)

2. Query operation: ask for the nearest marked ancestor of some node (the node itself also counts as its own ancestor).

Can you help her?

Input Format

The first line contains two positive integers $N$ and $Q$, denoting the number of nodes and the number of operations.

The next $N-1$ lines each contain two positive integers $u, v$ ($1 \leqslant u, v \leqslant N$) indicating a directed edge from $u$ to $v$. These edges form a rooted tree with root $1$, and edges are directed from parent to child.

The next $Q$ lines are of the form oper num. When oper is C, it denotes a mark operation on node num. When oper is Q, it denotes a query operation on node num.

Output Format

For each query operation, output one integer: the nearest marked ancestor of the given node (including the node itself). Print each answer on its own line.

5 5 
1 2 
1 3 
2 4 
2 5 
Q 2 
C 2 
Q 2 
Q 5 
Q 3

1
2
2
1

Hint

• 30% of the testdata: $1 \leqslant N, Q \leqslant 1000$.
• 70% of the testdata: $1 \leqslant N, Q \leqslant 10000$.
• 100% of the testdata: $1 \leqslant N, Q \leqslant 100000$.

Translated by ChatGPT 5