CF414E.Mashmokh's Designed Problem

After a lot of trying, Mashmokh designed a problem and it's your job to solve it.

You have a tree T with n vertices. Each vertex has a unique index from 1 to n. The root of T has index 1. For each vertex of this tree v, you are given a list of its children in a specific order. You must perform three types of query on this tree:

1. find distance (the number of edges in the shortest path) between u and v;
2. given v and h, disconnect v from its father and connect it to its h-th ancestor; more formally, let's denote the path from v to the root by _x_1, _x_2, ..., x__l (h < l), so that _x_1 = v and x__l is root; disconnect v from its father (_x_2) and connect it to x__h + 1; vertex v must be added to the end of the child-list of vertex x__h + 1;
3. in the vertex sequence produced by calling function dfs(root) find the latest vertex that has distance k from the root.

The pseudo-code of function dfs(v):

// ls[v]: list of children of vertex v
// its i-th element is ls[v][i]
// its size is size(ls[v])
sequence result = empty sequence;
void dfs(vertex now)
{
add now to end of result;
for(int i = 1; i <= size(ls[v]); i = i + 1) //loop from i = 1 to i = size(ls[v])
dfs(ls[v][i]);
}

经过多次尝试，Mashmokh 设计了一个问题，而你的任务就是解决它。

你有一棵包含 $ n $ 个顶点的树 $ T $。每个顶点具有一个从 $ 1 $ 到 $ n $ 的唯一编号。树 $ T $ 的根节点编号为 $ 1 $。对于该树中的每个顶点 $ v $，你被给定其子节点列表（按特定顺序排列）。你需要在该树上执行以下三类查询：

1. 求顶点 $ u $ 与 $ v $ 之间的距离（即最短路径所含边的数量）；
2. 给定顶点 $ v $ 和整数 $ h $，将 $ v $ 与其父节点断开连接，并将其连接至其第 $ h $ 个祖先节点；更准确地说，设从 $ v $ 到根节点的路径为 $ x_1,,x_2,,\dots,,x_l $（其中 $ h < l $），满足 $ x_1 = v $ 且 $ x_l $ 为根节点；则将 $ v $ 与其父节点（即 $ x_2 $）断开，并将其连接至 $ x_{h+1} $；顶点 $ v $ 必须被添加至顶点 $ x_{h+1} $ 的子节点列表末尾；
3. 在对 dfs(root) 函数调用所生成的顶点序列中，找出距离根节点为 $ k $ 的最后一个顶点。

函数 dfs(v) 的伪代码如下：

// ls[v]：顶点 v 的子节点列表
// 其第 i 个元素为 ls[v][i]
// 其长度为 size(ls[v])
sequence result = 空序列;
void dfs(vertex now)
{
    将 now 添加至 result 的末尾;
    for(int i = 1; i <= size(ls[v]); i = i + 1) // 循环从 i = 1 到 i = size(ls[v])
        dfs(ls[v][i]);
}

The first line of input contains two space-separated integers n, m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105), the number of vertices of T and number of queries to perform.

The i-th of the following n lines contains an integer l__i (0 ≤ l__i ≤ n), number of i-th vertex's children. Then l__i space-separated integers follow, the j-th of them is the index of j-th child of i-th vertex. Note that the order of these vertices is important.

Each of the following m lines has one of the following format: "1 v u", "2 v h", or "3 k". The first number in the line is the type of query to perform according to the problem statement. The next numbers are description of the query.

It's guaranteed that all the queries are correct. For example, in the second-type query h is at least 2 and at most distance of v from root. Also in the third-type query there is at least one vertex with distance k from the root at the time the query is given.

输入的第一行包含两个以空格分隔的整数 $n$、$m$（$2 \leq n \leq 10^5$；$1 \leq m \leq 10^5$），分别表示树 $T$ 的顶点数和需要执行的查询次数。

接下来的 $n$ 行中，第 $i$ 行包含一个整数 $l_i$（$0 \leq l_i \leq n$），表示第 $i$ 个顶点的子节点数目；随后是 $l_i$ 个以空格分隔的整数，其中第 $j$ 个整数表示第 $i$ 个顶点的第 $j$ 个子节点的编号。注意：这些子节点的顺序是重要的。

接下来的 $m$ 行每行具有以下三种格式之一：“1 $v$ $u$”、“2 $v$ $h$” 或 “3 $k$”。每行开头的数字表示该查询的类型（与题目描述一致）；后续数字为该查询的具体参数。

保证所有查询均合法。例如，在第二类查询中，$h$ 至少为 $2$，且至多为顶点 $v$ 到根节点的距离；在第三类查询中，在查询发出时，至少存在一个到根节点距离恰好为 $k$ 的顶点。

For each query of the first or third type output one line containing the result of the query.

对于每个第一类或第三类查询，输出一行，包含该查询的结果。