### 问题描述 A 公司的运营状况很不好，经常有人离职。成员的离职可能导致公司的分裂。这家公司初始 $n$ 名成员，其结构可以被看作一棵树，根结点是老板。如果 $a$ 号结点是 $b$ 号结点的父结点，则 $a$ 号成员是 $b$ 号成员的直接上司。一名成员 $x$ 离职后，他本人的结点和与其相连的边会被删除。由于公司管理混乱，新的边不会产生，其他成员之间直接上下属关系也不会变。于是 $x$ 所在的整棵树会分裂开，变成若干棵新的树。分裂得到每一棵树都是一个公司。 公司成员经常搞不清自己所在公司的老板是谁，因为所在树的分裂会产生新的根。于是原 A 公司推出了一个查询系统，用于处理以下两种请求： * 离职：成员 $s$ 的离职请求； * 查询：查询成员 $s$ 所在公司的老板是谁。 你需要处理 $m$ 条请求。 ### 输入格式 第一行包含 $2$ 个整数 $n$ 和 $m$，表示公司初始成员数量和请求数量。 接下来 $n-1$ 行，每行包含两个正整数 $a$ 和 $b$，表示 $a$ 是 $b$ 的直接上司。 接下来 $m$ 行，每行包含 $2$ 个正整数，表示一次请求。一次请求包含以下两种格式： ```text 1 s ``` 表示 $s$ 号成员离职； ```text 2 s ``` 表示查询 $s$ 号成员所在公司的老板。 ### 输出格式 对于每个查询请求，输出一行，包含一个整数，表示 $s$ 号员工所在公司的老板的编号。 ### 样例输入 ```text 3 3 1 2 2 3 2 3 1 2 2 3 ``` ### 样例输出 ```text 1 3 ``` ### 说明 在样例中，一开始 $2$ 号的上司是 $1$ 号，$3$ 号的上司是 $2$ 号。这时所有人的老板都是 $1$ 号。 $2$ 号离职后，$3$ 号成立一家新公司。这时 $3$ 号的老板是他自己。 ### 评测数据规模 对于 $50$% 的评测数据，$1\leq n,m \leq 10^3$。 对于 $100$% 的评测数据，$1\leq n,m \leq 10^5$，$1 \leq a, b, s \leq n$。保证输入是一棵有根树，所有成员最多只会离职一次，离职的成员不会出现在离职后的查询中。