F. Tree again
time limit per test
6 seconds
memory limit per test
256 megabytes
input
stdin
output
stdout

You are given a directed rooted tree T with N vertices (N ≤ 105). 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 ≤ 105):

  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.

Input

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).
Output

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

Examples
Input
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
Output
1
3
5
4
2
6
7
1
2
6
7
3
5
4
Note

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