### 问题描述

小齐有 $N$ 个贫瘠的牧场（$2 \leq N \leq 100,000$），通过 $N-1$ 条双向道路连接，确保任意两个牧场之间有且仅有一条路径。小牛贝茜喜欢悠闲地吃草，但她常常抱怨道路上没有草。小齐非常疼爱贝茜，今天他终于决定在道路上种植草地。他将使用一个包含 $M$ 步骤的程序（$1 \leq M \leq 100,000$）。

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

• 小齐会选择两个牧场，在它们之间的每条道路上种植一块草地。

• 贝茜会询问某条道路上有多少块草地，小齐必须回答她的问题。

小齐计算能够回答贝茜问题的次数，帮助他吧！

输入格式

• 第 $1$ 行: 两个用空格分隔的整数 $N$ 和 $M$。

• 接下来 $N$ 行：每行包含两个用空格分隔的整数，描述一条道路的两个端点。

• 接下来 $M$ 行：第 $i+1$ 行描述第 $i$ 步。该行的第一个字符是 $P$ 或 $Q$，分别表示小齐是在种植草地还是在询问。接下来是两个用空格分隔的整数 $A_i$ 和 $B_i$（$1 \leq A_i, B_i \leq N$），描述小齐的行动或查询。

输出格式

• 第 $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

样例输出

2
1
2

评测数据规模

$2 \leq N \leq 100,000$，$1 \leq M \leq 100,000$。