Description

【题意】
约翰有 N 个牧场，编号为 1 到 N 。
它们之间有 N−1 条道路，每条道路连接两个牧场。通过这些道路，所有牧场都是连通的。
刚开始的时候，所有道路都是光秃秃的，没有青草。约翰会在一些道路上批量种草。每次开始种草的时候，约翰会选择一个牧场作为起点，一个牧场作为终点，找到从起点到终点的最短路径，在这条路径上所有的道路上分别种下一棵新的青草。
贝西在监督约翰的工作，她迫不及待地想知道每条道路上已经有多少青草了。约翰的工作总是被贝西打断，他不胜其烦，所以请你来帮忙回答贝西的问题。约翰的工作和贝西的询问是穿插进行的，输入数据将会依次出现M个事件，以字符P开头的事件表示约翰在一条路径上种植了青草，以字符Q开头的事件表示贝西在查询一条道路上有多少青草。

【输入格式】
•第一行：两个整数 N 和 M ，2 ≤ N ≤ 10^6 , 1 ≤ M ≤ 10^6
•第二行到第 N 行：第 i+1 行有两个整数 Ui 和 Vi ，表示第 i 条道路连接的两个牧场编号，1 ≤ Ui , Vi ≤ N
•第 N+1 行到第 N+Q 行：每行首先由一个大写字母：
–如果是 P ，随后会有两个整数 A 和 B ，表示约翰在从A通向B的每条道路上都新种了一棵青草，1 ≤ A , B ≤N
–如果是 Q ，随后会有两个整数 A 和 B ，表示贝西查询一条道路上的青草数量， A 和 B 是这条道路的两个端点， $1 ≤ A,B ≤ N$，保证输入数据中存在一条A到B的道路

【输出格式】
•对每个查询请求，输出该条道路上青草的数量，以换行符分隔

【样例输入】
4 6
1 4
2 4
3 4
P 2 3
P 1 3
Q 3 4
P 1 4
Q 2 4
Q 1 4

【样例输出】
2
1
2