2860: 大树
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：0
题目描述
劳动节要到了，珂朵莉想去种树，但是由乃不想去。于是，由乃就给珂朵莉出了一道和树有关的题，如果珂朵莉能答对，由乃就陪珂朵莉种树。
有一颗根结点为 $1$ 的树，树可以进行一下两种操作。
1. 对某个结点图上颜色。（最开始只有结点 $1$ 有颜色，一个结点可以标记多次颜色。）
2. 询问某个结点最近的一个涂了颜色的祖先的编号是多少。（这个结点本身也算自己的祖先。）
你能帮帮珂朵莉吗？
有一颗根结点为 $1$ 的树，树可以进行一下两种操作。
1. 对某个结点图上颜色。（最开始只有结点 $1$ 有颜色，一个结点可以标记多次颜色。）
2. 询问某个结点最近的一个涂了颜色的祖先的编号是多少。（这个结点本身也算自己的祖先。）
你能帮帮珂朵莉吗？
输入
第一行两个正整数 $N$ 和 $Q$ 分别表示节点个数和操作次数。($1 \le N,Q \le 100000)
接下来 $N - 1$ 行，每行两个正整数 $u,v$(1 \le u,v \le n)表示 $u$ 到 $v$ 有一条边。
接下来 $Q$ 行，形如 `op x` ，`op` 为 `C` 时表示这是一个涂色操作, `op` 为 `Q` 时表示这是一个询问操作。
接下来 $N - 1$ 行，每行两个正整数 $u,v$(1 \le u,v \le n)表示 $u$ 到 $v$ 有一条边。
接下来 $Q$ 行，形如 `op x` ，`op` 为 `C` 时表示这是一个涂色操作, `op` 为 `Q` 时表示这是一个询问操作。
输出
对于每个询问操作，输出一个正整数，表示结果。
样例输入 复制
5 5
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3样例输出 复制
1
2
2
1