You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

居住在 ZOM 国度的小 S 已经完成了种树的基本目标，现在他要对他的树进行一些修改。

题目描述

​ 给定一棵 $n$ 个点的树和 $q$ 次操作，$1$ 为树的根，分为两种：

1. 给定 $u,v$，将 $u$ 的父亲修改为 $v$，保证 $u$ 是叶子结点。
2. 给定 $u,v$，查询 $u$ 和 $v$ 的最近公共祖先。

输入格式

第一行输入两个正整数 $n,q$。

第 $2\sim n$ 行，每行输入两个正整数 $u,v$，表示一条树边。

第 $n+1\sim n+q$ 行，每行三个正整数 $op,u,v$。其中 $op$ 表示操作种类，$u,v$ 含义如题面所述。

输出格式

对于每一个查询操作，输出一行一个整数，表示你的答案。

样例 #1

样例输入 #1

3 3
1 2
1 3
2 2 3
1 3 2 
2 2 3

样例输出 #1

1
2

提示

存在大样例，请检查文件。

对于 $30\%$ 的数据，保证 $1\leq n,q\leq 1000$

对于 $60\%$ 的数据，保证 $1\leq n,q\leq 2\times 10^5$

对于另外 $10\%$ 的数据，保证不存在操作 $1$。

对于 $100\%$ 的数据，保证 $1\leq n,q\leq 10^6$，所有输入均合法。