题目描述

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

• C x：给结点 $x$ 打上标记（在最开始，只有结点 $1$ 有标记，其他结点均无标记，而且对于某个结点，可以打多次标记）。
• Q x：询问结点 $x$ 最近的一个打了标记的祖先的编号（这个结点本身也算自己的祖先）。

你能帮帮他吗?

输入格式

输入第一行，两个正整数 $n$ 和 $q$，分别表示节点个数和操作次数。
接下来 $n-1$ 行，每行两个正整数 $u,v$（$1 \leq u,v \leq n$）表示有一条从 $u$ 到 $v$ 的边。
接下来 $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

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n,q \leq 10^5$。