白黑树

【题目描述】

给定一棵有根树，树根为1

要求支持以下操作：

1、M u:把u节点反色(即黑色变成白色，白色变成黑色）

2、Q u:查询u和所有黑色节点的所有LCA中深度最小的LCA

【输入格式】

第一行n，m 表示节点总数和操作次数

以下n-1行，每行u，v描述一条边的两个端点

以下m行，每行一个操作，如题意所示

一开始，树上节点都是白色的

n，m<=200000

【输出格式】

对于每个Q询问，如果树上没有黑色节点，输出-1

否则输出对应的答案

【样例输入】

5 5
2 1
3 1
4 1
5 4
Q 5
M 3
Q 3
Q 2
M 1

【样例输出】

-1
3
1