401607: GYM100499 F Tree again

You are given a directed rooted tree T with N vertices (N ≤ 10⁵). The vertices are numbered from 1 to N, with vertex 1 being the root. You must perform Q queries of two types on the tree (Q ≤ 10⁵):

1. Given 2 vertices u and v, disconnect u from its father and make u the last child of vertex v. For this type of query, it is guaranteed that u is not an ancestor of v.
2. find the kth vertex of the pre-order tree traversal.

The pre-order tree traversal can be explained by this pseudo-code and figure.

The first line of input contains the only integer T - number of test cases (T ≤ 10). Then T tests follow. For each test case:

• First line contains the only integer N.
• Next N - 1 lines, each line contains 2 integers x and y indicating that y is a child of x. The children of x appear in correct order.
• Next line contains the only integer Q.
• Next Q lines contain descriptions of the queries, in one of the two formats:
  • 1 u v (1 ≤ u, v ≤ N) and it is guaranteed that u is not an ancestor of v
  • 2 k (1 ≤ k ≤ N).

For each query of type , print one line containing the only integer - the answer of the query.

1
7
1 3
1 2
3 5
3 4
2 6
2 7
15
2 1
2 2
2 3
2 4
2 5
2 6
2 7
1 3 2
2 1
2 2
2 3
2 4
2 5
2 6
2 7

1
3
5
4
2
6
7
1
2
6
7
3
5
4

The query type 2 in example can be explained by the following figure: