k-ий пращур#9629

k-ий пращур

4 секунди

128 мегабайтів

Легка

Дерево з $p$ вершинами є зв'язним графом з $p - 1$ p - 1 ребром. Позначимо $r$ як корінь дерева. Якщо вершина $a$ знаходиться на відстані $l$ від $r$ , а вершина $b$ на відстані $l + 1$ l + 1 від $r$ , і $a$ з'єднано з $b$ , то $a$ називається пращуром (предком) $b$ (тобто батьківською вершиною).

Аналогічно, якщо $a$ знаходиться на відстані $l$ від $r$ і $b$ на відстані $l + k$ l + k від $r$ , і існує шлях довжиною $k$ від $a$ до $b$ , то $a$ називається $k$ -им пращуром $b$ .

Сьюзен любить грати з графами, і дерево є однією з її улюблених структур даних. Вона створила задачу і хоче дізнатися, чи зможе хтось її вирішити. Іноді вона додає або видаляє вершину, яка є листком. Ваше завдання — в будь-який момент знайти $k$ -го пращура вершини.

Вхідні дані

Перша стрічка містить кількість тестів $t$ ( $1 \leq t \leq 3$ 1 \le t \le 3). Далі йдуть $t$ тестів. Перша стрічка кожного тесту містить кількість вершин $p$ ( $1 \leq p \leq 1 0^{5}$ 1 \le p \le 10^5) у дереві. Кожна з наступних $p$ стрічок містить два цілі числа $x$ і $y$ , що означає, що $y$ є пращуром (предком) $x$ . Якщо $y$ дорівнює $0$ , то $x$ є коренем дерева ( $0$ не належить дереву). Відомо, що $1 \leq x, y \leq 1 0^{5}$ 1 \le x, y \le 10^5.

Наступна стрічка містить кількість запитів $q$ ( $1 \leq q \leq 1 0^{5}$ 1 \le q \le 10^5). Кожна з наступних $q$ стрічок містить запит:

- $0$ $y$ $x$ : $x$ додається як новий листок з пращуром $y$ . $x$ ще не в дереві, $y$ належить дереву. - $1$ $x$ : вершина-листок $x$ видаляється з дерева. $x$ є листком дерева. - $2$ $x$ $k$ : виведіть $k$ -го ( $1 \leq k \leq 1 0^{5}$ 1 \le k \le 10^5) пращура $x$ . $x$ — вершина в дереві.

Вихідні дані

Для кожного запиту типу $2$ виведіть $k$ -го пращура $x$ . Якщо $k$ -ий пращур не існує, виведіть $0$ . Якщо вказана вершина не існує, виведіть $0$ .

Приклади

Приклад 1