# k-th ancestor

A tree of p nodes is an undirected connected graph having p - 1 edges. Let us denote r as the root node. If a is a node such that it is at a distance of l from r, and b is a node such that it is at at distance of l + 1 from r and a is connected to b, then we call a as the parent of b.

Similarly, if a is at a distance of l from r and b is at a distance of l + k from r and there is a path of length k from a to b, then we call a as the k-th parent of b.

Susan likes to play with graphs and Tree data structure is one of her favorites. She has designed a problem and wants to know if anyone can solve it. Sometimes she adds or removes a leaf node. Your task is to figure out the k-th parent of a node at any instant.

## Input

The first line contain an integer t (1 ≤ t ≤ 3) denoting the number of test cases. t test cases follow. First line of each test case contains an integer p (1 ≤ p ≤ `10^5`

), the number of nodes in the tree. p lines follows each containing two integers x and y separated by a single space denoting y as the parent of x. If y is 0, then x is the root node of the tree. (0 is for namesake and is not in the tree). It is known that 1 ≤ x, y ≤ `10^5`

.

The next line contains an integer q (1 ≤ q ≤ `10^5`

), the number of queries. q lines follow each containing a query.

0 y x: x is added as a new leaf node whose parent is y. x is not in the tree while y is in.

1 x: This tells that leaf node x is removed from the tree. x is a leaf in the tree.

2 x k: In this query output the k-th (1 ≤ k ≤

`10^5`

) parent of x. x is a node in the tree.

## Output

For each query of type 2, output the k-th parent of x. If k-th parent doesn't exist, output 0 and if the node doesn't exist, output 0.