eolymp
bolt
Try our new interface for solving problems
Problems

k-th ancestor

k-th ancestor

Time limit 4 seconds
Memory limit 128 MiB

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 data

The first line contain an integer t (1t3) denoting the number of test cases. t test cases follow. First line of each test case contains an integer p (1p10^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 1x, y10^5.

The next line contains an integer q (1q10^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 (1k10^5) parent of x. x is a node in the tree.

Output data

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.

Examples

Input example #1
2
7
2 0
5 2
3 5
7 5
9 7
8 2
6 8
10
0 5 15
2 15 2
1 3
0 15 20
0 20 13
2 13 4
2 13 3
2 6 10
2 11 1
2 9 1
1
10000 0
3
0 10000 4
1 4
2 4 1
Output example #1
2
2
5
0
0
7
0