题目描述

$\red{Farmer John }$有 $\red{N }$个贫瘠的牧场（$\red{2 <= N <= 100,000）}$，由 $\red{N-1 }$条双向道路连接，因此任何两个牧场之间只有一条路径。$\red{Bessie }$是一头热爱放牧时光的母牛，经常抱怨牧场之间的道路上没有草。农夫约翰非常爱贝西，今天他终于要在马路上种草了。他将使用包含 $\red{M }$个步骤 $\red{(1 <= M <= 100,000) }$的过程来执行此操作。

在每一步都会发生以下两种情况之一：

$\red{FJ}$将选择两个牧场，并在两个牧场之间的每条道路上种植一块草，或者，

$\red{Bessie }$会询问某条路上有多少草丛，而 $\red{Farmer John }$必须回答她的问题。

农夫约翰是个很差劲的柜台一一帮他回答贝西的问题！

输入格式

第 $\red{1 }$行：两个空格分隔的整数 $\red{N }$和 $\red{M}$

第 $\red{2..N }$行：两个用空格分隔的整数，描述道路的端点。

第 $\red{N+1..N+M }$行：第 $\red{i+1 }$行描述步骤 $\red{i}$。该行的第一个字符是$\red{P}$或$\red{Q，}$它描述了$\red{FJ}$是在种草还是简单地查询。

接下来是两个以空格分隔的整数 $\red{A_i }$和 $\red{B_i (1 <= A_i, B_i <= N)，}$它们描述了 $\red{FJ }$的操作或查询。

输出格式

$\red{Lines 1..???：}$每一行都有一个查询的答案，出现的顺序与输入中出现的查询相同。

样例

输入样例

4 6 
1 4 
2 4 
3 4 
磷 2 3
1 3
问 3 4
1 4
问 2 4
问 1 4

输出样例

2
1
2

提示

对于 $\red{100\%}$的数据，$\red{2≤}$$\red{n≤}$$\red{10^5，}$$\red{1≤M}$$\red{≤}$$\red{10^5}$