Description

As a birthday gift from drd, atm recently got a Russian matryoshka doll. He is very interested in how it is constructed.

A matryoshka doll is nested layer by layer. Assume that: inside a matryoshka doll of size $x$, it is possible to put any number of matryoshka dolls with sizes smaller than $x$ (while matryoshka dolls sold in the market usually allow only one smaller doll inside a bigger one).

drd tells atm that this matryoshka doll is made up of $n$ small dolls, and their sizes are all different. We label these small dolls by size from small to large as $1$ to $n$.

If atm wants to view the small doll of size $k$, he will first check whether this doll is already on the table. If it is already on the table, then he can view it. Otherwise, he will open some matryoshka doll on the table, take out all small dolls directly inside it, and place them on the table.

At the beginning, there is only the doll of size $n$ (given by drd) on the table. Note that each time he opens a doll, he only takes out all small dolls directly inside it. If a small doll taken out still contains other dolls inside, he will not take out those deeper dolls.

Also, atm has an obsessive need for optimality. He will minimize the number of dolls he needs to open.

atm is a strange person. Sometimes he only wants to know how many dolls need to be opened to view the doll of size $x$ (but does not actually open them). Sometimes, after hearing from drd that a doll is especially beautiful, he will open it to view it. Now please output how many dolls he needs to open each time.

Input Format

The first line contains two integers $n,m$, representing the number of dolls and the number of operations atm wants to perform.

The next $n-1$ lines each contain two integers $u,v$, meaning that inside the doll of size $u$ there is a doll of size $v$. It is guaranteed that $u>v$.

The next $m$ lines each are in one of the following forms:

• P x: atm must view the doll of size $x$ (this will open $x$, and opening $x$ is not counted in the total answer);

• Q x: atm only wants to know how many dolls he would need to open in order to view the doll of size $x$, but he does not actually open them.

Output Format

Output $m$ lines. For each P operation or Q operation in the input, output the number of matryoshka dolls that need to be opened (or hypothetically opened).

5 5
5 3
5 4
3 2
3 1
Q 1
Q 4
P 2
Q 1
Q 4

2
1
2
0
0

Hint

For $30\%$ of the testdata: $n,m \le 1000$.

For $100\%$ of the testdata: $n,m \le 100000$.

Translated by ChatGPT 5