Trees and Derivatives

Adrian is a Computer Science student. Few of the courses that he took last year were Data Structures
and Algorithms. He likes to play with Trees and its derivatives. With lot of research he has designed
a problem and wants to know if anyone can solve it.
He starts with:
A tree of N nodes is an undirected connected graph having N1 edges. Let there be
a root node R. If R1 is a node such that it is at a distance of L from R, and R2
is a node such that it is at a distance L+1 from R and R1 is connected to R2,
then we call R1 as parent of R2. If R1 is at a distance of L and R2 is at a distance
L+i from R then we call R1 as ith parent of R2.
End of story.
Sometime, Adrian adds or removes a leaf node.Your inevitable task is to
find out the ith parent of a node at any instant.
Input
The first line contains T, denoting the number of test cases.T test cases follow.
First line of each test case contains N, number of nodes in the tree.
N lines follow each containing two integers P and Q separated by single space
denoting Q as parent of P. If Q is 0, then P is root node of the tree. Node 0 doesn't exist in the tree.
The next line contains an integer C, denoting the number of queries.
C lines follow each containing a query.
 0 Q P: Q is in the tree while P isn't.P is added as a new leaf node whose parent is Q.
 1 P: P is a leaf in the tree. This tells that leaf node P is removed from the tree.
 2 P I:P is a node in the tree. Output the Ith parent of P.
>
>
Output
For each query of type 2, output a single line containing the Ith parent of P.If Ith parent doesn't exist or
if the node doesn't exist output 0 in both case.
 If you have multiple test cases in a file start this section as: "For each test case, output a single line containing...".
>Tips:
 If you have multiple test cases in a file start this section as: "For each test case, output a single line containing...".
>
Constraints
 1 ≤ T ≤ 3
 1 ≤ N ≤ 10^{5}
 1 ≤ C ≤ 10^{5}
 1 ≤ P ≤ 10^{5}
 1 ≤ Q ≤ 10^{5}
 1 ≤ I ≤ 10^{5}
Example
Input: 2 7 2 0 5 2 3 5 7 5 9 8 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: 2 2 5 0 0 8 0
Explanation
Example case 1.
The tree has 7 nodes with 2 as its root. There are 10 queries:
>0 5 15 > 15 is added as a leaf node to 5.
>2 15 2 > 2nd parent of 15 is 15>5>2 is 2.
>1 3 > leaf node 3 is removed from the tree.
>0 15 20 > 20 is added as a leaf node to 15.
>0 20 13 > 13 is added as a leaf node to 20.
>2 13 4 > 4th parent of 13 is 2.
>2 13 3 > 3rd parent of 13 is 5.
>2 6 10 > there is no 10th parent of 6 and hence 0.
>2 11 1 > 11 is not a node in the tree, hence 0.
>2 9 1 > 9's parent is 8.
Example case 2.
The second test case has a tree with only one node(10000).
>0 10000 4 > 4 is added as a leaf node to 10000.
>1 4 > 4 is removed.
>2 4 1 > as 4 is already removed, answer is 0.
Author:  harshitbansal3 
Tags  harshitbansal3 
Date Added:  18012016 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 