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.