A tree of $\mbox{P}$ nodes is an un-directed connected graph having $P-1$ edges. Let us denote $\mbox{R}$ as the root node. If $\mbox{A}$ is a node such that it is at a distance of $\boldsymbol{\mbox{L}}$ from $\mbox{R}$, and $\mbox{B}$ is a node such that it is at at distance of $L+1$ from 
$\mbox{R}$ and $\mbox{A}$ is connected to $\mbox{B}$, then we call $\mbox{A}$ as the parent of $\mbox{B}$. 

Similarly, if $\mbox{A}$ is at a distance of $\boldsymbol{\mbox{L}}$ from $\mbox{R}$ and $\mbox{B}$ is at a distance of $L+K$ from $\mbox{R}$ and there is a path of length $\mbox{K}$ from $\mbox{A}$ to $\mbox{B}$, then we call $\mbox{A}$ as the $\mbox{K}^{th} $parent of $\mbox{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 $\mbox{K}^{th} $parent of a node at any instant.

Input Format

The first line contain an integer $\mathbf{T}$ denoting the number of test cases. $\mathbf{T}$ test cases follow. First line of each test case contains an integer $\mbox{P}$, the number of nodes in the tree.
$\mbox{P}$ lines follows each containing two integers $\mbox{X}$ and $\mathbf{Y}$ separated by a single space denoting $\mathbf{Y}$ as the parent of $\mbox{X}$. If $\mathbf{Y}$ is $\mbox{0}$, then X is the root node of the tree.  ($\mbox{0}$ is for namesake and is not in the tree). 

The next line contains an integer $\mbox{Q}$, the number of queries. 

$\mbox{Q}$ lines follow each containing a query.  

$\mbox{0}$ $\mathbf{Y}$ $\mbox{X}$  : $\mbox{X}$ is added as a new leaf node whose parent is $\mathbf{Y}$ . $\mbox{X}$ is not in the tree while $\mathbf{Y}$ is in. 
$\mbox{1}$ $\mbox{X}$     : This tells that leaf node $\mbox{X}$ is removed from the tree. $\mbox{X}$ is a leaf in the tree. 
$2$ $\mbox{X}$ $\mbox{K}$   : In this query output the $\mbox{K}^{th}$ parent of $\mbox{X}$ . $\mbox{X}$ is a node in the tree. 

Note 

Each node index is any number between 1 and 10^{5} i.e., a tree with a single node can have its root indexed as 10^{5}

Constraints

$1\leq T\leq3$ 

$1\leq P\leq10^5$ 

$1\leq Q\leq10^5$ 

$1\leq X\leq10^5$ 

$\textbf{0}\leq Y\leq10^5$ 

$1\leq K\leq10^5$  

Output Format

For each query of type $2$, output the $\mbox{K}^{th} $parent of $\mbox{X}$. If $\mbox{K}^{th} $parent doesn't exist, output $\mbox{0}$ and if the node doesn't exist, output $\mbox{0}$.

Sample 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

Sample Output
2
2
5
0
0
8
0

Explanation

There are 2 test cases. The first test case 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.  

the second testcase has a tree with only 1 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.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Graph algorithms


Solutions:
def go():
	I = lambda : map(int, input().split())
	N = 100002
	d = [0] * N
	P = [0] * N

	def add(p, c):
		d[c] = d[p] + 1
		v = [p]
		for i in range(17):
			if not P[p] or len(P[p]) <= i:
				break
			p = P[p][i]
			v.append(p)
		P[c] = v
	c = [[] for i in range(N)]
	for i in range(next(I())):
		(x, y) = I()
		if y:
			c[y].append(x)
		else:
			R = x
	l = [R]
	while l:
		p = l.pop()
		l.extend(c[p])
		for h in c[p]:
			add(p, h)
	del c, l
	for i in range(next(I())):
		l = list(I())
		if l[0] > 1:
			(_, x, k) = l
			if d[x] < k:
				print(0)
				continue
			for i in range(17):
				if 1 << i & k:
					x = P[x][i]
			print(x)
		elif l[0]:
			d[l[1]] = 0
		else:
			add(l[1], l[2])
for t in range(int(input())):
	go()


from collections import defaultdict
T = int(input())
for _ in range(T):
	P = int(input())
	tree = defaultdict(tuple)
	for _ in range(P):
		(X, Y) = map(int, input().split())
		if len(tree[Y]) < 1000:
			tree[X] = tree[Y] + (Y,)
		else:
			tree[X] = (Y,)
	Q = int(input())
	for _ in range(Q):
		vals = list(map(int, input().split()))
		if len(vals) == 2:
			X = vals[1]
			tree.pop(X)
		else:
			op = vals[0]
			if op == 0:
				(Y, X) = vals[1:]
				if len(tree[Y]) < 1000:
					tree[X] = tree[Y] + (Y,)
				else:
					tree[X] = (Y,)
			else:
				(X, K) = vals[1:]
				if X not in tree:
					print(0)
					continue
				while 1:
					if len(tree[X]) >= K:
						print(tree[X][len(tree[X]) - K])
						break
					K -= len(tree[X])
					X = tree[X][0]
					if X == 0:
						print(0)
						break


import collections
import queue
import math
MAX_N = 10 ** 5
MAX_STEP = int(math.ceil(math.log2(MAX_N))) + 1

def solve():
	p = int(input().strip())
	tree = collections.defaultdict(set)
	ancestors = {0: [0] * MAX_STEP}
	for i in range(p):
		(x, y) = [int(p) for p in input().strip().split()]
		ancestors[x] = [0] * MAX_STEP
		ancestors[x][1] = y
		tree[y].add(x)
	q = queue.Queue()
	root = 0
	q.put(root)
	while not q.empty():
		item = q.get()
		for s in range(2, MAX_STEP):
			u = s - 1
			p = ancestors[item][u]
			if not p:
				break
			ancestors[item][s] = ancestors[p][u]
		for child in tree[item]:
			q.put(child)
	queries = int(input().strip())
	for qq in range(queries):
		cmd = [int(p) for p in input().strip().split()]
		if cmd[0] == 0:
			(y, x) = (cmd[1], cmd[2])
			ancestors[x] = [0] * MAX_STEP
			ancestors[x][1] = y
			for s in range(2, MAX_STEP):
				u = s - 1
				p = ancestors[x][u]
				if not p:
					break
				ancestors[x][s] = ancestors[p][u]
		elif cmd[0] == 1:
			del ancestors[cmd[1]]
		else:
			(x, k) = (cmd[1], cmd[2])
			if x in ancestors:
				step = 1
				while k:
					bit = k & 1
					if bit:
						x = ancestors[x][step]
					step += 1
					k >>= 1
			else:
				x = 0
			print(x)
t = int(input().strip())
for tt in range(t):
	solve()


from collections import defaultdict, deque
import sys
MAX_P = 10 ** 5

def read_line():
	return (int(x) for x in sys.stdin.readline().split())

def add(parents, depths, node, parent):
	depth = depths[parent] + 1
	depths[node] = depth
	div = 1
	parents[node] = []
	for a in parents[parent]:
		if depths[parent] % div:
			parents[node].append(a)
		else:
			parents[node].append(parent)
		div *= 10

def query(parents, depths, node, k):
	if depths[node] < k:
		print(0)
		return
	target = depths[node] - k
	i = 5
	while depths[node] > target:
		if depths[parents[node][i]] >= target:
			node = parents[node][i]
		else:
			i -= 1
	print(node)
for _ in range(int(input())):
	children = defaultdict(list)
	root = None
	for _ in range(int(input())):
		(x, y) = read_line()
		children[y].append(x)
	parents = [None] * (MAX_P + 1)
	parents[0] = [0] * 6
	depths = [-1] * (MAX_P + 1)
	que = deque([(children[0][0], 0)])
	while que:
		(node, parent) = que.popleft()
		add(parents, depths, node, parent)
		for child in children[node]:
			que.append((child, node))
	for _ in range(int(input())):
		(q, *params) = read_line()
		if q == 0:
			(parent, child) = params
			add(parents, depths, child, parent)
		elif q == 1:
			parents[params[0]] = None
			depths[params[0]] = -1
		else:
			query(parents, depths, *params)


class Vertex:

	def __init__(self, val, parent, dp):
		self.val = val
		self.parent = parent
		self.dp = dp

class Ancestor:

	def __init__(self, init_edges, trunk=None):
		self.verts = {}
		self.trunk = trunk or init_edges[0][0]
		self.dph = {}
		self.layer_parents(init_edges)

	def layer_parents(self, init_edges):
		(dp, frontier, tiers) = (0, [0], {0: 0})
		while frontier:
			new_frontier = []
			for u in frontier:
				if u in init_edges:
					for v in init_edges[u]:
						if v not in tiers:
							tiers[v] = dp
							new_frontier.append(v)
							self.add_initedge(v, u, dp)
			frontier = new_frontier
			dp += 1
		return

	def add_initedge(self, v, parent, dp):
		self.verts[v] = Vertex(v, parent, dp)
		if dp > 0:
			if dp in self.dph:
				self.dph[dp].append(v)
			else:
				self.dph[dp] = [v]
		return

	def add_edge(self, new_edge):
		(kid, parent) = new_edge
		depth = self.verts[parent].dp
		self.verts[kid] = Vertex(kid, parent, depth + 1)
		return

	def k_ancestor(self, v, nth):
		if v not in self.verts:
			return 0
		if self.trunk == v or self.verts[v].dp < nth:
			return 0
		if self.verts[v].dp == nth:
			return self.trunk
		start_dp = self.verts[v].dp
		(nth_dp, vid) = (start_dp - nth, v)
		dph_nodes = self.dph[nth_dp]
		len_dph_nodes = len(dph_nodes)
		if len_dph_nodes == 1:
			vid = dph_nodes[0]
		else:
			for _ in range(start_dp, nth_dp, -1):
				vid = self.verts[vid].parent
		return vid

	def cut_leaf(self, vid):
		if vid in self.verts:
			del self.verts[vid]
		return

def main():
	for (edges, qrys) in get_input():
		genealog = Ancestor(edges)
		del edges
		for (i, qi) in enumerate(qrys):
			if qi[0] == 0:
				genealog.add_edge((qi[2], qi[1]))
			elif qi[0] == 1:
				genealog.cut_leaf(qi[1])
			else:
				kth_v_ancestor = genealog.k_ancestor(qi[1], qi[2])
				print(kth_v_ancestor)
	return 1

def get_input():
	nT = int(input().strip())
	for _ in enumerate(range(nT)):
		nP = int(input().strip())
		pnodes = [[] for n in range(nP)]
		for n in range(nP):
			pnodes[n] = list(map(int, input().split()))
		nQ = int(input().strip())
		qrys = [[] for n in range(nQ)]
		for n in range(nQ):
			qrys[n] = list(map(int, input().split()))
		pt_table = {p[1]: [] for p in pnodes}
		for (vi, pi) in sorted(pnodes, key=lambda x: x[1]):
			pt_table[pi].append(vi)
		yield (pt_table, qrys)
main()


N = int(100000.0)

def add_node(tree, parent, node):
	tree[node] = list(gen_parents(tree, parent))

def remove_node(tree, x):
	tree[x] = None

def gen_parents(tree, node):
	yield node
	i = 0
	while True:
		parents = tree[node]
		if parents is None or i >= len(parents):
			return
		node = parents[i]
		yield node
		i += 1

def construct_tree(children):
	tree = [None] * (N + 1)
	root = children[0][0]
	stack = [root]
	tree[root] = []
	while stack:
		node = stack.pop()
		parents = list(gen_parents(tree, node))
		if children[node] is None:
			continue
		for c in children[node]:
			tree[c] = parents
			stack.append(c)
	return tree

def binary(x):
	i = 0
	while x > 0:
		if x % 2:
			yield i
		x //= 2
		i += 1

def ancestor(tree, node, k):
	for i in binary(k):
		parents = tree[node]
		if parents is None or i >= len(parents):
			return 0
		node = parents[i]
	return node
t = int(input())
for _ in range(t):
	children = [None] * (N + 1)
	p = int(input())
	for _ in range(p):
		(x, y) = [int(x) for x in input().split()]
		if children[y] is None:
			children[y] = [x]
		else:
			children[y].append(x)
	tree = construct_tree(children)
	q = int(input())
	for _ in range(q):
		u = [int(x) for x in input().split()]
		if len(u) == 2:
			assert u[0] == 1
			remove_node(tree, u[1])
		elif len(u) == 3:
			if u[0] == 0:
				add_node(tree, *u[1:])
			elif u[0] == 2:
				print(ancestor(tree, *u[1:]))


from math import log

def largestPowTwoExp(n):
	return int(log(n, 2))

def addNode(X, Y):
	if Y != 0:
		nodes[X].append(Y)
		ind = 0
		cur = Y
		while ind < len(nodes[cur]):
			nodes[X].append(nodes[cur][ind])
			cur = nodes[cur][ind]
			ind += 1
T = int(input())
for t in range(T):
	nodes = [list() for i in range(pow(10, 5) + 1)]
	P = int(input())
	for p in range(P):
		(X, Y) = map(int, input().split())
		addNode(X, Y)
	Q = int(input())
	for q in range(Q):
		inp = list(map(int, input().split()))
		if inp[0] == 0:
			addNode(inp[2], inp[1])
		elif inp[0] == 1:
			nodes[inp[1]] = []
		elif inp[0] == 2:
			(X, K) = (inp[1], inp[2])
			cur = X
			while K > 0:
				p = largestPowTwoExp(K)
				if p < len(nodes[cur]):
					cur = nodes[cur][p]
				else:
					cur = 0
					break
				K -= pow(2, p)
			print(cur)


import sys
from math import log2
t = int(input())
for t_itr in range(t):
	p = int(input())
	tree = {}
	jump = {}
	for treeIndex in range(p):
		(nodeId, parent) = map(int, input().rstrip().split())
		tree[treeIndex] = nodeId
		jump[nodeId] = [parent]
	log2p = int(log2(p)) + 1
	for jumpIndex in range(1, log2p):
		for treeIndex in range(p):
			try:
				jump[tree[treeIndex]].append(jump[jump[tree[treeIndex]][jumpIndex - 1]][jumpIndex - 1])
			except KeyError:
				jump[tree[treeIndex]].append(0)
	query = []
	ADD = 0
	DELETE = 1
	KTHANCESTOR = 2
	q = int(input())
	for _ in range(q):
		query = list(map(int, input().rstrip().split()))
		command = query[0]
		if command == ADD:
			parent = query[1]
			leaf = query[2]
			jump[leaf] = [parent]
			for jumpIndex in range(1, log2p):
				try:
					jump[leaf].append(jump[jump[leaf][jumpIndex - 1]][jumpIndex - 1])
				except:
					if leaf in jump:
						jump[leaf].append(0)
					else:
						jump[leaf] = 0
		elif command == DELETE:
			nodeId = query[1]
			for jumpIndex in range(len(jump[nodeId])):
				jump[nodeId][jumpIndex] = 0
		elif command == KTHANCESTOR:
			nodeId = query[1]
			k = query[2]
			jumpIndex = 0
			while nodeId > 0 and k > 0:
				if k & 1:
					try:
						nodeId = jump[nodeId][jumpIndex]
					except:
						nodeId = 0
				k >>= 1
				jumpIndex += 1
			print(nodeId)


tree = None

class Node:

	def __init__(self, nr, parent):
		if parent == -1:
			self.nr = nr
			self.parent = None
			self.wys = 0
			self.parents = [None] * 17
			return
		assert tree[parent]
		self.nr = nr
		self.parent = tree[parent]
		self.wys = self.parent.wys + 1
		self.parents = list(self.parent.parents)
		for b in range(17):
			if not self.wys & 1 << b:
				self.parents[b] = self
				break
T = int(input())
for t in range(T):
	P = int(input())
	tree = [None] * 100001
	tree[0] = Node(0, -1)
	jeszcze = []
	for p in range(P):
		(x, y) = map(int, input().split())
		jeszcze.append((x, y))
	while jeszcze:
		jeszcze2 = []
		for (x, y) in jeszcze:
			if tree[y] is not None:
				tree[x] = Node(x, y)
			else:
				jeszcze2.append((x, y))
		jeszcze = jeszcze2
	Q = int(input())
	res = ''
	for q in range(Q):
		spl = list(map(int, input().split()))
		if spl[0] == 0:
			tree[spl[2]] = Node(spl[2], spl[1])
		elif spl[0] == 1:
			tree[spl[1]] = None
		elif not tree[spl[1]]:
			print(0)
			continue
		else:
			tr = tree[spl[1]]
			ten = tr.wys
			docelowy = ten - spl[2]
			if docelowy <= 0:
				print(0)
				continue
			for bt in range(17, -1, -1):
				if ten & 1 << bt and (not docelowy & 1 << bt):
					tr = tr.parents[bt]
					ten = tr.wys
				elif not ten & 1 << bt and docelowy & 1 << bt:
					assert False
			print(tr.nr)


import math
T = int(input())
max_size = 10 ** 5 + 1
max_log_size = int(math.log(max_size, 2)) + 1
for _ in range(T):
	parents = [[0] * max_log_size for _ in range(max_size)]
	nodes = set()
	P = int(input())
	for _ in range(P):
		(X, Y) = input().split()
		(X, Y) = (int(X), int(Y))
		nodes.add(X)
		nodes.add(Y)
		parents[X][0] = Y
	for jump in range(1, max_log_size):
		for n in nodes:
			parents[n][jump] = parents[parents[n][jump - 1]][jump - 1]
	Q = int(input())
	for _ in range(Q):
		q = input().split()
		if q[0] == '0':
			(Y, X) = (int(q[1]), int(q[2]))
			parents[X][0] = Y
			for jump in range(1, max_log_size):
				parents[X][jump] = parents[parents[X][jump - 1]][jump - 1]
		elif q[0] == '1':
			X = int(q[1])
			for jump in range(0, max_log_size):
				parents[X][jump] = 0
		else:
			(X, K) = (int(q[1]), int(q[2]))
			i = 0
			while K > 0:
				if K & 1:
					X = parents[X][i]
				i += 1
				K >>= 1
			print(X)


def get_tree():
	P = int(input())
	C = []
	for i in range(P):
		(X, Y) = map(int, input().split())
		Z = max(X, Y)
		while len(C) <= Z:
			C.append([])
		C[X].append(Y)
		C[Y].append(X)
	V = bytearray(len(C))
	V[0] = 1
	A = [0] * len(C)
	L = [0]
	while L:
		i = L.pop()
		for j in C[i]:
			if not V[j]:
				V[j] = 1
				A[j] = i
				L.append(j)
	return [A]

def add(x, y, A):
	for B in A:
		while len(B) <= x:
			B.append(0)
		B[x] = y
		y = B[y]

def remove(x, A):
	if x < len(A[0]):
		for B in A:
			B[x] = 0

def kth_parent(k, x, A):
	if x >= len(A[0]):
		return 0
	i = 0
	while k:
		if len(A) <= i:
			B = A[-1]
			A.append([B[y] for y in B])
		if k & 1:
			x = A[i][x]
		k >>= 1
		i += 1
	return x

def do_queries(A):
	Q = int(input())
	for q in range(Q):
		L = [int(x) for x in input().split()]
		T = L[0]
		if T == 0:
			add(L[2], L[1], A)
		elif T == 1:
			remove(L[1], A)
		elif T == 2:
			print(kth_parent(L[2], L[1], A))
T = int(input())
for t in range(T):
	do_queries(get_tree())


import math

class Node:

	def __init__(self, index):
		self.index = index
		self.children = []
		self.ancestors = []

def construct_ancestors_for_node(node):
	if node.ancestors:
		current = node.ancestors[0]
		depth = 0
		while current:
			if current.ancestors and depth < len(current.ancestors):
				node.ancestors.append(current.ancestors[depth])
				current = current.ancestors[depth]
				depth += 1
			else:
				current = None

def construct_ancestors(root, num_nodes):
	stack = [root]
	while stack:
		current = stack.pop()
		construct_ancestors_for_node(current)
		if current.children:
			for child in current.children:
				stack.append(child)

def insert_new_node(nodes, index, parent):
	nodes[index] = Node(index)
	nodes[index].ancestors = [nodes[parent]]
	construct_ancestors_for_node(nodes[index])

def delete_leaf(nodes, index):
	nodes[index] = None

def query_kth_ancestor(node, k):
	depth = 0
	while k > 0 and node:
		if k % 2:
			if depth < len(node.ancestors):
				node = node.ancestors[depth]
			else:
				return 0
		depth += 1
		k //= 2
	if node:
		return node.index
	return 0
test_cases = int(input())
for _ in range(test_cases):
	num_nodes = int(input())
	nodes = [None for i in range(pow(10, 5) + 1)]
	root_node = -1
	for _ in range(num_nodes):
		(node, parent) = list(map(int, input().split()))
		if parent == 0:
			root_node = node
			nodes[node] = Node(node)
		else:
			if not nodes[node]:
				nodes[node] = Node(node)
			if not nodes[parent]:
				nodes[parent] = Node(parent)
			nodes[parent].children.append(nodes[node])
			nodes[node].ancestors.append(nodes[parent])
	construct_ancestors(nodes[root_node], num_nodes)
	queries = int(input())
	for _ in range(queries):
		query = list(map(int, input().split()))
		if query[0] == 0:
			insert_new_node(nodes, query[2], query[1])
		elif query[0] == 1:
			delete_leaf(nodes, query[1])
		elif query[0] == 2:
			print(query_kth_ancestor(nodes[query[1]], query[2]))


import math
import os
import random
import re
import sys
import datetime

class Solution(object):

	@staticmethod
	def findParents(n, q, edges, queries):
		tree = {}
		parents = {}
		result = []
		i = 0
		root = -1
		for e in edges:
			if e[1] == 0:
				root = e[0]
				break
		while i < len(edges):
			if edges[i][1] not in tree:
				tree[edges[i][1]] = []
			tree[edges[i][1]].append(edges[i][0])
			i += 1
		newq = []
		queue = [root]
		while len(queue) > 0:
			curr = queue.pop()
			if curr not in tree:
				continue
			for ch in tree[curr]:
				queue.append(ch)
				newq.append([0, curr, ch])
		for q in queries:
			newq.append(q)
		for q in newq:
			if q[0] == 0:
				Solution.addtotree(q[2], q[1], parents)
			elif q[0] == 1:
				del parents[q[1]]
			elif q[0] == 2:
				result.append(Solution.findparent(q[1], q[2], parents))
		return result

	@staticmethod
	def addtotree(x, y, parents):
		parents[x] = {1: y}
		curr = 1
		while parents[x][curr] in parents and curr in parents[parents[x][curr]]:
			parents[x][curr + curr] = parents[parents[x][curr]][curr]
			curr += curr

	@staticmethod
	def findparent(x, k, parents):
		if x not in parents:
			return 0
		curr = 1
		while k > 0:
			while curr + curr <= k:
				curr += curr
			k -= curr
			if x not in parents or curr not in parents[x]:
				return 0
			x = parents[x][curr]
			curr = 1
		return x
T = int(input())
while T > 0:
	edges = []
	n = int(input())
	for _ in range(n):
		edges.append(list(map(int, input().rstrip().split())))
	queries = []
	q = int(input())
	for _ in range(q):
		queries.append(list(map(int, input().rstrip().split())))
	result = Solution.findParents(n, q, edges, queries)
	for r in result:
		print(str(r))
	T -= 1


from collections import defaultdict, deque
import sys
MAX_P = 10 ** 5

def read_line():
	return (int(x) for x in sys.stdin.readline().split())

def add(parents, depths, node, parent):
	depth = depths[parent] + 1
	depths[node] = depth
	div = 1
	parents[node] = []
	for a in parents[parent]:
		if depths[parent] % div:
			parents[node].append(a)
		else:
			parents[node].append(parent)
		div *= 10

def query(parents, depths, node, k):
	if depths[node] < k:
		print(0)
		return
	target = depths[node] - k
	i = 5
	while depths[node] > target:
		if depths[parents[node][i]] >= target:
			node = parents[node][i]
		else:
			i -= 1
	print(node)
for _ in range(int(input())):
	children = defaultdict(list)
	root = None
	for _ in range(int(input())):
		(x, y) = read_line()
		children[y].append(x)
	parents = [None] * (MAX_P + 1)
	parents[0] = [0] * 6
	depths = [-1] * (MAX_P + 1)
	que = deque([(children[0][0], 0)])
	while que:
		(node, parent) = que.popleft()
		add(parents, depths, node, parent)
		for child in children[node]:
			que.append((child, node))
	for _ in range(int(input())):
		(q, *params) = read_line()
		if q == 0:
			(parent, child) = params
			add(parents, depths, child, parent)
		elif q == 1:
			parents[params[0]] = None
			depths[params[0]] = -1
		else:
			query(parents, depths, *params)


import sys
import math
from typing import Deque
sys.setrecursionlimit(1000000)

class Node:

	def __init__(self, i, depth, children, ancestors):
		self.i = i
		self.depth = depth
		self.children = set(children)
		self.ancestors = list(ancestors)

def print_graph(G):
	for X in G:
		node = G[X]
		print(node)
	print()

def dfs(G, u):
	node = G[u]
	if node.ancestors[0] != 0:
		log = math.floor(math.log(node.depth, 2))
		for i in range(1, log + 1):
			ancestor = G[node.ancestors[i - 1]]
			if not len(ancestor.ancestors) > i - 1:
				break
			node.ancestors.append(ancestor.ancestors[i - 1])
	for v in node.children:
		child = G[v]
		child.depth = node.depth + 1
		dfs(G, v)

def dfs_stack(G, u):
	stack = Deque([u])
	while stack:
		u = stack.pop()
		node = G[u]
		if node.ancestors[0] != 0:
			log = math.floor(math.log(node.depth, 2))
			for i in range(1, log + 1):
				ancestor = G[node.ancestors[i - 1]]
				if not len(ancestor.ancestors) > i - 1:
					break
				node.ancestors.append(ancestor.ancestors[i - 1])
		for v in node.children:
			child = G[v]
			child.depth = node.depth + 1
			stack.append(v)
T = int(sys.stdin.readline())
for _ in range(T):
	P = int(sys.stdin.readline())
	S = set()
	G = [None] * 100001
	for _ in range(P):
		(X, Y) = list(map(int, sys.stdin.readline().strip().split(' ')))
		S.add(X)
		if Y == 0:
			G[X] = Node(X, 0, [], [0])
		else:
			G[X] = Node(X, 0, [], [Y])
	root = None
	for X in S:
		node = G[X]
		if node.ancestors[0] != 0:
			parent = G[node.ancestors[0]]
			parent.children.add(X)
		else:
			root = X
	dfs_stack(G, root)
	Q = int(sys.stdin.readline())
	for _ in range(Q):
		q = list(map(int, sys.stdin.readline().strip().split(' ')))
		if q[0] == 0:
			(Y, X) = q[1:]
			parent = G[Y]
			node = Node(X, parent.depth + 1, [], [Y])
			G[X] = node
			dfs_stack(G, X)
		elif q[0] == 1:
			X = q[1]
			node = G[X]
			G[X] = None
		elif q[0] == 2:
			(X, K) = q[1:]
			a = 0
			if G[X] is not None:
				node = G[X]
				k = K
				while k > 0:
					log = math.floor(math.log(k, 2))
					if not len(node.ancestors) > log or not node.ancestors[log] != 0:
						a = 0
						break
					node = G[node.ancestors[log]]
					a = node.i
					k -= 2 ** log
			print(a)


import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def MI():
	return map(int, input().split())
from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	up = defaultdict(lambda : [0 for i in range(20)])
	nodes = []
	for i in range(n):
		(x, y) = MI()
		nodes.append(x)
		up[x][0] = y
	for i in range(1, 20):
		for j in nodes:
			if up[j][i - 1]:
				up[j][i] = up[up[j][i - 1]][i - 1]
	for __ in range(int(input())):
		q = list(MI())
		if q[0] == 0:
			up[q[2]][0] = q[1]
			for j in range(1, 20):
				if up[q[2]][j - 1]:
					up[q[2]][j] = up[up[q[2]][j - 1]][j - 1]
		elif q[0] == 1:
			del up[q[1]]
		else:
			(cur, k) = (q[1], q[2])
			for j in range(20):
				if 1 << j & k:
					cur = up[cur][j]
					if cur == 0:
						break
			print(cur)


from sys import stdin
from math import ceil, log2

class Node:
	__slots__ = ['d', 'v', 'ps']

	def __init__(self, v, ps, d):
		self.v = v
		self.d = d
		self.ps = ps

class FakeTree:

	def __init__(self, n):
		self.shifts = [ceil(log2(i)) for i in range(1, n + 10)]

	def add_root(self, v):
		self.root = v
		self.ch_p = {v: Node(v=v, ps=[0], d=1)}

	def add_child_to(self, ch, p):
		if p not in self.ch_p:
			self.add_child_to(p, self.root)
		pd = self.ch_p[p]
		new_d = pd.d + 1
		parents = [pd.v]
		for j in range(1, self.shifts[new_d]):
			parents.append(self.ch_p[parents[j - 1]].ps[j - 1])
		ch_d = Node(ch, ps=parents, d=new_d)
		self.ch_p[ch] = ch_d
		return True

	def remove(self, value):
		del self.ch_p[value]

	def print_kth_parent_of(self, k, child):
		if child in self.ch_p:
			node = self.ch_p[child]
			depth = node.d
			if depth <= k:
				print(0)
				return False
			for j in range(self.shifts[k] + 1):
				if k & 1 << j:
					nn = node.ps[j]
					node = self.ch_p[nn]
			print(node.v)
			return True
		print(0)
lns = stdin.read().strip().splitlines()
ln = 0
tc = int(lns[ln])
ln += 1
ft = None
for _ in range(tc):
	n = int(lns[ln])
	ft = FakeTree(n)
	ln += 1
	for _ in range(n):
		(ch, p) = map(int, lns[ln].split())
		ln += 1
		if p == 0:
			ft.add_root(ch)
			continue
		ft.add_child_to(ch, p)
	q = int(lns[ln])
	ln += 1
	for _ in range(q):
		(n, *vs) = map(int, lns[ln].split())
		ln += 1
		if n == 0:
			ft.add_child_to(vs[1], vs[0])
		elif n == 1:
			ft.remove(vs[0])
		elif n == 2:
			ft.print_kth_parent_of(vs[1], vs[0])