经过多次尝试,Mashmokh 设计了一个问题,你的工作就是解决它。
你有一棵有 n 个顶点的树 T。每个顶点都有一个从 1 到 n 的唯一索引。 T 的根的索引为 1。对于该树 v 的每个顶点,都会按特定顺序给出其子节点的列表。您必须对此树执行三种类型的查询:
1.求u和v之间的距离(最短路径中的边数);
2.给定v和h,断开v与其父亲的连接并将其连接到其第h个祖先;更正式地,我们用 x1, x2, ..., xl (h < l) 表示从 v 到根的路径,因此 x1 = v 并且 xl 是根;将 v 与其父 (x2) 断开并将其连接到 xh + 1;顶点 v 必须添加到顶点 xh + 1 的子列表的末尾;
3. 在调用函数 dfs(root) 产生的顶点序列中,找到距根的距离为 k 的最新顶点。
函数dfs(v)的伪代码:
输入
输入的第一行包含两个空格分隔的整数 n、m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105)、T 的顶点数和要执行的查询数。
以下 n 行中的第 i 行包含一个整数 li (0 ≤ li ≤ n),即第 i 个顶点的子节点数。然后是 li 个空格分隔的整数,其中第 j 个是第 i 个顶点的第 j 个子节点的索引。请注意,这些顶点的顺序很重要。
以下 m 行中的每一行都具有以下格式之一:“1 v u”、“2 v h”或“3 k”。行中的第一个数字是根据问题陈述执行的查询类型。接下来的数字是查询的描述。
保证所有查询都是正确的。例如,在第二类查询中,h 与根的距离至少为 2,且至多为 v。同样,在第三种类型的查询中,在给出查询时,至少有一个距根的距离为 k 的顶点。
输出
对于第一或第三类型的每个查询,输出一行包含查询结果。
示例
输入 #1
4 9 1 2 1 3 1 4 0 1 1 4 2 4 2 1 3 4 3 1 3 2 2 3 2 1 1 2 3 1 3 2
输出 #1
3 2 2 4 1 3 4
输入 #2
2 2 1 2 0 1 2 1 3 1
输出 #2
1 2