k-ый предок
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 ≤ 105
) вершин в дереве. Каждая из следующих p строк содержит два целых числа x и y означающих что y является предком x. Если y равно 0, то x корень дерева (0 не принадлежит дереву). Известно, что 1 ≤ x, y ≤ 105
.
Следующая строка содержит количество запросов q (1 ≤ q ≤ 105
). Каждая из следующих q строк содержит запрос.
- 0 y x: x добавляется новым листом с предком y. x еще не в дереве, y принадлежит дереву.
- 1 x: вершина-лист x удаляется из дерева. x является листом дерева.
- 2 x k: выведите k-го (1 ≤ k ≤
105
) предка x. x - вершина в дереве.
Выходные данные
Для каждого запроса типа 2 выведите k-го предка x. Если k-ый предок не существует, выведите 0. Если указанная вершина не существует, выведите 0.
2 7 2 0 5 2 3 5 7 5 9 7 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
2 2 5 0 0 7 0