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.