劳动节要到了，珂朵莉想去种树，但是由乃不想去。于是，由乃就给珂朵莉出了一道和树有关的题，如果珂朵莉能答对，由乃就陪珂朵莉种树。

有一颗根结点为 $1$ 的树，树可以进行一下两种操作。

1. 对某个结点图上颜色。（最开始只有结点 $1$ 有颜色，一个结点可以标记多次颜色。）

2. 询问某个结点最近的一个涂了颜色的祖先的编号是多少。（这个结点本身也算自己的祖先。）

你能帮帮珂朵莉吗？

输入

第一行两个正整数 和 分别表示节点个数和操作次数。(接下来 $N - 1$行，每行两个正整数 u,v表示 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

求代码