A tree of nodes is an un-directed connected graph having edges. Let us denote as the root node. If is a node such that it is at a distance of from , and is a node such that it is at at distance of from
and is connected to , then we call as the parent of .
Similarly, if is at a distance of from and is at a distance of from and there is a path of length from to , then we call as the th parent of .
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 th parent of a node at any instant.
The first line contain an integer denoting the number of test cases. test cases follow. First line of each test case contains an integer , the number of nodes in the tree.
lines follows each containing two integers and separated by a single space denoting as the parent of . If is , then X is the root node of the tree. ( is for namesake and is not in the tree).
The next line contains an integer , the number of queries.
lines follow each containing a query.
: is added as a new leaf node whose parent is . is not in the tree while is in.
: This tells that leaf node is removed from the tree. is a leaf in the tree.
: In this query output the th parent of . is a node in the tree.
Each node index is any number between 1 and 105 i.e., a tree with a single node can have its root indexed as 105
For each query of type , output the th parent of . If th parent doesn't exist, output and if the node doesn't exist, output .