Farm Management

There are $N$ farms connected by $N-1$ two-way roads. Between any two farms there is exactly one path; in other words, the farms and roads form a tree. The farms are numbered from $1$ to $N$.

Jaehyun wants to plant trees along the roads. The work is given as queries, and there are two kinds:

• P u v: plant one tree on every road along the path between farm $u$ and farm $v$.
• Q u v: print the total number of trees planted on the roads along the path between farm $u$ and farm $v$.

Initially no road has any tree planted on it. Process the queries in order.

The first line contains the number of farms $N$ and the number of queries $M$. ($1 \le N, M \le 100{,}000$)

Each of the next $N-1$ lines contains the numbers of the two farms connected by a road, one road per line.

Each of the following $M$ lines contains one query, consisting of a single character (P or Q) and two integers $u$ and $v$, in the format described above.

For each Q query, print on its own line the number of trees planted on the roads along the given path.