题目描述

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

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

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

初始边权均为 0。

输入格式

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

2 
1 
2

说明/提示

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