Муравей живет около дерева, а точнее, у самого его корня. Дерево состоит из n узлов и n - 1 ветки, каждая ветка соединяет пару узлов. Двигаясь по веткам, Муравей может попасть в любой узел дерева. Все узлы дерева пронумерованы от 1 до n, корень имеет номер 1.
Время от времени Муравей совершает вылазки за пищей. Перед каждой вылазкой он узнает v1, v2, ..., vk — номера узлов дерева, в которых есть пища. Муравей собирается обойти все эти узлы. Он начинает свой путь из корня дерева, затем, двигаясь по веткам дерева, обходит все узлы с пищей в произвольном порядке и возвращается обратно в корень дерева.
Жизнь Муравья не слишком легка, поскольку он постоянно подвергается опасности: за ним охотится Дятел! А именно, если Муравей во время своего пути побывает в каком-либо узле более двух раз, то он рискует быть замеченным дятлом. В этом случае Муравей будет спасаться бегством. В таком случае он прерывает обход дерева и возвращается в корень кратчайшим способом. Чем больше расстояние от узла, в котором его заметил Дятел, до корня, тем хуже. Муравей хочет найти такой обход узлов с пищей, который бы минимизировал это расстояние в худшем для Муравья случае.
Напишите программу, которая определяет наибольшее из расстояний от корня до узла, в котором Муравья может заметить Дятел, если Муравей перемещается оптимальным способом. Вам будет дано несколько описаний вылазок Муравья, найдите искомую величину для каждой из вылазок.
Кроме того, дерево не является полностью статичным. Оно может изменяться:
Входные данные состоят из одного или нескольких тестовых наборов.
Первая строка каждого тестового набора содержит число n (2 ≤ n ≤ 105) — количество узлов в дереве в начальный момент времени. Вторая строка содержит описание дерева на начальный момент времени. Описание состоит из n - 1 целого числа p2, ..., pn, где pi (2 ≤ i ≤ n) — номер узла, из которого Муравей придет в узел i при движении от корня. Гарантируется, что входные данные описывают корректное дерево с узлами, занумерованными от единицы до n.
Далее записано число m (1 ≤ m ≤ 105) — количество запросов. Запросы могут описывать одно из трех событий: вылазка Муравья, добавление узла и удаление поддерева. Каждая из следующих m строк описывает очередной запрос в одном из следующих форматов:
».Муравей должен посетить k узлов с заданными различными номерами v1, v2, ..., vk (порядок обхода этих узлов выбирает Муравей). В ответ на этот запрос требуется вывести наибольшее расстояние от корня, на котором может оказаться Муравей в момент, когда его заметит Дятел (или выведите - 1, если Муравей может совершить обход без риска быть замеченным дятлом).
Гарантируется, что узлы с номерами v1, ..., vk существуют в дереве непосредственно перед выполнением данного запроса.
».В дерево добавляется новый узел, соединенный с одним из уже существующих. Новый узел получает номер, равный наименьшему натуральному числу, которое не является номером никакого узла в текущий момент. Этот узел соединяется веткой с узлом номер x + y, где y — результат последнего запроса типа 1. Гарантируется, что хотя бы один запрос типа 1 уже произведен, и что узел с номером x + y существует в дереве непосредственно перед выполнением данного запроса. Число x в запросе может быть произвольным целым числом.
».Из дерева удаляется узел v вместе со всем своим поддеревом. Поддеревом этого узла следует считать все такие узлы дерева, посещению которых обязательно предшествует посещение v при движении от корня. Обратите внимание на то, что номера удаленных узлов освобождаются, и могут быть вновь использованы для добавляемых узлов в последующих запросах типа 2. Гарантируется, что узел v существует непосредственно перед выполнением данного запроса. Также гарантируется, что v > 1, то есть корень дерева удален быть не может.
Сумма чисел k по всем запросам типа 1 внутри одного тестового набора не превосходит 105.
Для каждого набора тестовых данных выведите строку с номером набора и последовательностью ответов на запросы первого типа. Гарантируется, что каждый набор тестовых данных будет содержать хотя бы один запрос первого типа. Запросы следует обрабатывать в порядке их следования в описании тестового набора.
3
1 1
4
? 2 2 3
+ 2
+ 2
? 3 2 4 5
2
1
4
? 2 1 2
? 1 2
- 2
? 1 1
5
3 1 1 3
4
? 2 2 5
- 2
+ 0
? 2 2 5
Case 1: 0 1
Case 2: -1 -1 -1
Case 3: 1 0
