题目描述
FarmerJohn有 N个贫瘠的牧场(2<=N<=100,000),由 N−1条双向道路连接,因此任何两个牧场之间只有一条路径。Bessie是一头热爱放牧时光的母牛,经常抱怨牧场之间的道路上没有草。农夫约翰非常爱贝西,今天他终于要在马路上种草了。他将使用包含 M个步骤 (1<=M<=100,000)的过程来执行此操作。
在每一步都会发生以下两种情况之一:
FJ将选择两个牧场,并在两个牧场之间的每条道路上种植一块草,或者,
Bessie会询问某条路上有多少草丛,而 FarmerJohn必须回答她的问题。
农夫约翰是个很差劲的柜台一一帮他回答贝西的问题!
输入格式
第 1行:两个空格分隔的整数 N和 M
第 2..N行:两个用空格分隔的整数,描述道路的端点。
第 N+1..N+M行:第 i+1行描述步骤 i。该行的第一个字符是P或Q,它描述了FJ是在种草还是简单地查询。
接下来是两个以空格分隔的整数 Ai和 Bi(1<=Ai,Bi<=N),它们描述了 FJ的操作或查询。
输出格式
Lines1..???:每一行都有一个查询的答案,出现的顺序与输入中出现的查询相同。
样例
输入样例
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≤105,1≤M≤105