题目描述

在你帮助 Deni 求出了公司“Deni Monopoly”的拓扑序数量之后，她又遇到了一个新任务。公司管理层偶尔也会做出理智的决定，于是他们改变了原先奇怪的组织结构。现在，公司被表示为一棵有根树，共有 N 名员工，编号为 1..N，其中 1 号员工是公司老板。

不过管理层仍然不完全满意，于是要求 Deni 继续调整当前的组织结构。

这里，“某员工的上级”既包括直接上级，也包括间接上级；“某员工的下属”也同样包括直接下属和间接下属。

Deni 可以进行的操作是：把某个员工的直接上级改成另一个员工。当然，她不会做出荒谬的改动，例如把某人的直接上级改成他自己，或者改成他自己的某个下属。获得新上级的员工会连同自己原有的整个子树一起移动，子树内部层级关系保持不变。

为了评估结构变化，她会询问任意两名员工的最近公共上级是谁。

由于一次调整不可能立刻得到理想的组织结构，因此 Deni 一共会进行 Q 次操作和询问（统称“请求”）。

请编写程序 restructuring，处理这些请求。

输入格式

第一行一个正整数 N，表示员工总数。
接下来 N-1 行，每行两个不同的整数 x 和 y，表示员工 x 是员工 y 的直接上级（即 y 是 x 的直接下属）。

接下来一行一个正整数 Q，表示请求数。
随后 Q 行，每行是以下两种格式之一：

• 1 y x：修改请求，令 x 成为 y 的新直接上级。题目保证在该请求中总有 x ≠ y，并且在修改前 x 不是 y 的下属。
• 2 x y：询问请求，求 x 和 y 在当前组织结构下按层级意义的最近公共上级。每个员工都被认为是自己的上级，因此该类请求中可能出现 x = y，或者 x 与 y 存在祖先—后代关系。

输出格式

对于每个类型为 2 的请求，输出一行一个整数，表示答案员工的编号。

数据范围

• 1 ≤ N, Q ≤ 100000

子任务

只有通过某个子任务中的全部测试点，才能获得该子任务的分数。

样例输入

5
1 2
1 3
2 4
2 5
8
2 4 3
2 5 5
2 1 2
1 2 3
2 4 3
2 4 5
1 4 3
2 4 5

样例输出

1
5
1
3
2
3