特殊权利
题号:NC202988
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

    2020年1月1日,2020BITACMClub公司正式成立啦!

    2020BITACMClub公司现在拥有个员工,为了更好地管理这些员工,公司决定设立级别管理制度。每个人可以负责管理某些人,也可以被某个人所管理。管理关系可以看作一颗有根树,树的根节点拥有最高级别,级别按树深度依次向下递减。管理关系具有传递性,即编号为的员工可以管理以为根节点的子树中(包括他自己)的所有员工。本题中树的根节点代表编号为的员工。

    公司的员工们都很喜欢打比赛。为了更好地组织公司内部的比赛,公司又决定在某些时刻赋予某个员工一项特殊的权利------创建比赛。如果某个员工拥有一道好题,他必须将题目交给他的某个能够管理他且拥有这项特殊权利的人,自己的题目才能用作比赛。但员工们又都不希望招惹级别太高的人,因此员工们很希望能够找出在当前能够管理自己且拥有这项特殊权利的员工中级别最小的一个。起初整个公司仅编号为的员工拥有特殊权利。

    公司保证每次只可能进行两种操作:


  1. 对编号为的员工赋予特殊权利;
  2. 询问能够管理编号为的员工且拥有特殊权利的员工中级别最小的一个是谁。


输入描述:

第一行输入两个数,分别代表公司员工的数量和公司操作数。

接下来行,每行两个正整数,代表编号为的员工管理编号为的员工。

再接下来行,每行格式为""。如果为'',表示编号为的员工被赋予特殊权利;如果为'',表示员工希望知道自己应该把题目交给谁。

输出描述:

对于每个的输入,输出一个正整数,表示查询结果的员工编号。
示例1

输入

复制
5 5
1 2
1 3
2 4
2 5
Q 2
C 2
Q 2
Q 5
Q 3

输出

复制
1
2
2
1

备注:

注意员工可以将题目上交给自己(如果满足题目条件的话)。