7. 树

【题目描述】

在 2016 年，佳媛姐姐刚刚学习了树，非常开心。现在她想解决这样一个问题：给定一颗有根树，根为 $1$，有以下两种操作：

1. 标记操作：对某个结点打上标记。（在最开始，只有结点 $1$ 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记。）

2. 询问操作：询问某个结点最近的一个打了标记的祖先（这个结点本身也算自己的祖先）。

你能帮帮她吗？

【输入格式】

第一行两个正整数 $N$ 和 $Q$ 分别表示节点个数和操作次数。

接下来 $N-1$ 行，每行两个正整数 $u,v$（$1 \leq u,v \leq n$）表示 $u$ 到 $v$ 有一条有向边。

接下来 $Q$ 行，形如 oper num，oper 为 C 时表示这是一个标记操作，oper 为 Q 时表示这是一个询问操作。

【输出格式】

对于每个询问操作，输出一行，一个正整数，表示结果。

【样例 1 输入】

5 5 
1 2 
1 3 
2 4 
2 5 
Q 2 
C 2 
Q 2 
Q 5 
Q 3

【样例 1 输出】

1
2
2
1

【数据范围】

$30\%$ 的数据，$1 \leq N, Q \leq 1000$；

$70\%$ 的数据，$1 \leq N, Q \leq 10000$；

$100\%$ 的数据，$1 \leq N, Q \leq 100000$。