Description

给出一棵有 $n$ 个节点的树，有 $m$ 个如下所示的操作：

• 将两个节点之间的路径上的边的权值均加一。

• 查询两个节点之间的那一条边的权值，保证两个节点直接相连。

初始边权均为 $0$。

Input Format

第一行两个整数 $n,m$，含义如上。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示 $u,v$ 之间有一条边。

接下来 $m$ 行，每行格式为 op u v，$op=\texttt{P}$ 代表第一个操作，$op=\texttt{Q}$ 代表第二个操作。

Output Format

若干行。对于每个查询操作，输出一行整数，代表查询的答案。

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 

Hint

对于 $100\%$ 的数据，$2\le n\le 10^5$，$1\le m\le 10^5$。