k-ый предок
Дерево с p вершинами представляет собой связный граф с p - 1 ребром. Обозначим через r корень дерева. Если a - вершина на расстоянии l от r, а b - вершина на расстоянии l + 1 от r, при этом a соединено с b, то будем a называть предком b.
Аналогично если a находится на расстоянии l от r и b на расстоянии l + k от r, и существует путь длины k от a до b, то будем называть a k-ым предком b.
Сьюзен любит играть с графами, а структура данных Дерево - одна из ее любимых. Она сделала задачу и хочет знать, сможет ли кто-нибудь решить ее. Иногда она добавляет или удаляет вершину, являющуюся листом. Ваша задача - в любой момент найти k-го предка вершины.
Входные данные
Первая строка содержит количество тестов t (1 ≤ t ≤ 3). Далее следуют t тестов. Первая строка каждого теста содержит количество p (1 ≤ p ≤ 10^5) вершин в дереве. Каждая из следующих p строк содержит два целых числа x и y означающих что y является предком x. Если y равно 0, то x корень дерева (0 не принадлежит дереву). Известно, что 1 ≤ x, y ≤ 10^5.
Следующая строка содержит количество запросов q (1 ≤ q ≤ 10^5). Каждая из следующих q строк содержит запрос.
0 y x: x добавляется новым листом с предком y. x еще не в дереве, y принадлежит дереву.
1 x: вершина-лист x удаляется из дерева. x является листом дерева.
2 x k: выведите k-го (1 ≤ k ≤
10^5) предка x. x - вершина в дереве.
Выходные данные
Для каждого запроса типа 2 выведите k-го предка x. Если k-ый предок не существует, выведите 0. Если указанная вершина не существует, выведите 0.