Byteotian Country Roads

In old Byteotia, there were n villages (numbered from 1 to n) connected by bidirectional dirt roads forming a tree. The roads were built so that for any village, there is exactly one simple route to village 1 (Bitburg) and this route only passes through villages having numbers not greater than that of the starting village. In other words, for each edge connecting two villages u and v, if u<v then u is the unique parent of v in the tree.

Initially every road is a country road with weight 1 (representing one country road to walk), but with time every country road was replaced by a motorway. In our problem the state of a road is reflected in its weight: a road that has not been replaced still has weight 1, and after replacement its weight becomes 0.

You are given the tree structure and a sequence of m+n-1 queries. Each query is one of the following two types:

• A x y: At this moment the country road between villages x and y is replaced by a motorway, i.e. the weight of the edge is set to 0. Note that by the tree construction the parent is always the vertex with the smaller index (i.e. if x < y then x is the parent of y). Each edge is updated exactly once.
• W x: Byteasar starts his journey from Bitburg (village 1) to village x. Calculate the sum of the weights of the edges along the unique path from village 1 to village x. This is equal to the number of country roads (i.e. roads still with weight 1) that Byteasar had to walk.

The problem guarantees that there are exactly n-1 update (A) queries and m query (W) operations. The input format is as follows.

---

Problem Input Format

The first line contains two integers n and m separated by a space.

The following n-1 lines each contain two integers x and y describing an edge between villages x and y.

The next m+n-1 lines each contain a query in one of the two forms:

• A x y
• W x

---

Problem Output Format

For each W query, output a single line with the sum of the weights on the path from village 1 to village x.

---

Note: All formulas below are written in \( \LaTeX \) format. For example, the number of villages is given by \( n \) and the initial weight of every edge is \( 1 \).

inputFormat

The input begins with two integers \( n \) and \( m \) (1 \le n \le ...), separated by a space.

Then follow \( n-1 \) lines, each with two integers x and y (\(1 \le x,y \le n\)) representing an edge between villages x and y. By the problem property, the parent of an edge is the vertex with the smaller number.

After that, there are \( m+n-1 \) lines each containing a query. A query is of one of the following two types:

• A x y: Update the weight of the edge connecting x and y to \(0\).
• W x: Query the sum of the weights on the path from village \(1\) to village \(x\).

outputFormat

For each query of type W, output a single integer on a new line which is the sum of the edge weights along the unique path from village \(1\) to the queried village.

sample

3 2
1 2
1 3
W 2
A 1 2
W 2
W 3

1
0
1

</p>