题目描述

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

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

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

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

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

输入格式

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

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

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

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

输出格式

${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

提示

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