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₁, x₂, ..., x_l (h < l), so that x₁ = v and x_l is root; disconnect v from its father (x₂) 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]);
}