SP12005 GRASSPLA - Grass Planting

约翰有 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 + M 行：每行首先由一个大写字母： 如果是 P，随后会有两个整数 A 和 B，表示约翰在从 A 通向 B 的每条道路上都新种了一棵青草， 1 ≤ A， B ≤ N。 如果是 Q，随后会有两个整数 A 和 B，表示贝西查询一条道路上的青草数量， A 和 B 是这条道路的两个端点， 1 ≤ A， B ≤ N，保证输入数据中存在一条 A 到 B 的道路。

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