E. Интерактивная игра с раскраской
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача. Не забывайте о том, что ваша программа должна каждый раз после вывода запроса сбрасывать буфер вывода. Для сброса буфера вывода можно использовать fflush(stdout) в C++, system.out.flush() в Java, stdout.flush() в Python или flush(output) в Pascal. Если вы используете другой язык программирования, посмотрите в его документации, как выполняется эта операция. Также рекомендуем вам прочесть руководство по интерактивным задачам: https://codeforces.me/blog/entry/45307.

Дано дерево с $$$n$$$ вершинами; вершина $$$1$$$ является корнем дерева. Для каждого $$$i \in [2, n]$$$ вам дан родитель $$$i$$$-й вершины $$$p_i$$$; для каждой вершины соблюдается $$$p_i < i$$$.

Вам предстоит раскрасить все ребра дерева, используя минимально возможное количество цветов, таким образом, чтобы выиграть в игру на этом дереве (каждое ребро должно быть окрашено в ровно один цвет).

Игра, в которую мы собираемся играть, будет проходить следующим образом. После того как вы раскрасите ребра и выведите их цвета, жюри поместит фишку в одну из вершин дерева (кроме корня). Ваша цель — переместить эту фишку в корень ровно за $$$d$$$ ходов, где $$$d$$$ — расстояние от вершины до корня (расстояние равно количеству ребер на пути). Если фишка достигает корня за $$$d$$$ ходов, вы выигрываете. В противном случае вы проигрываете.

Жюри не сообщит вам, где находится фишка. Вы даже не будете знать значение $$$d$$$ заранее. Однако в начале каждого хода вам будет сообщено, сколько ребер каждого цвета инцидентно текущей вершине (это включает как ребро, ведущее вверх по дереву, так и ребра, ведущие вниз). Вы должны выбрать один из этих цветов, и фишка будет перемещена вдоль ребра выбранного цвета (если есть несколько ребер с этим цветом, жюри выбирает одно из них). После перемещения фишки вам снова будет сообщена та же информация о текущей вершине, и игра продолжается, пока вы не достигнете корня или не сделаете $$$d$$$ ходов, не достигнув корня.

Интерактор для этой задачи является адаптивным. Это означает, что начальная вершина и текущая вершина не фиксированы и могут изменяться «на ходу» в зависимости от вывода вашей программы. Однако состояние игры всегда будет согласовано с информацией, которую вы получаете: всегда будет как минимум одна начальная вершина и как минимум один путь вашей фишки из этой вершины, согласующийся как с информацией о цветах, которую вы получаете, так и с цветами, которые вы выбирали во время ходов.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$3 \le n \le 100$$$) — количество вершин в дереве.

Вторая строка содержит $$$n-1$$$ целых чисел $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i < i$$$), где $$$p_i$$$ — родитель $$$i$$$-й вершины в дереве.

Протокол взаимодействия

Сначала вы должны вывести выбранную вами раскраску ребер следующим образом:

  • в первой строке выведите одно целое число $$$k$$$ ($$$1 \le k \le n - 1$$$) — количество используемых вами цветов;
  • во второй строке выведите $$$n-1$$$ целых чисел $$$c_2, c_3, \dots, c_n$$$ ($$$1 \le c_i \le k$$$), где $$$c_i$$$ — цвет ребра, соединяющего вершины $$$p_i$$$ и $$$i$$$.

Затем начинается игра. В начале каждого хода программа жюри выводит что-то одно из следующего:

  • целое число $$$1$$$ на отдельной строке, указывающее, что фишка достигла корня, и вы выиграли;
  • целое число $$$-1$$$ на отдельной строке, указывающее, что вы не достигли корня за $$$d$$$ ходов и проиграли, или вы сделали что-то неправильно (либо раскраска, которую вы предоставили, не соответствует ограничениям, либо ваш предыдущий ход невозможен);
  • или целое число $$$0$$$ на отдельной строке, за которым следует строка, содержащая $$$k$$$ целых чисел $$$e_1, e_2, \dots, e_k$$$, где $$$e_i$$$ — количество ребер с цветом $$$i$$$, инцидентных текущей вершине.

Если вы получаете $$$1$$$ или $$$-1$$$, ваша программа должна немедленно завершиться, в противном случае вердикт для вашей посылки может быть неопределенным. Если вы получаете $$$0$$$, за которым следуют $$$k$$$ целых чисел $$$e_1, e_2, \dots, e_k$$$, вы должны вывести одно целое число, указывающее цвет, который вы выбираете во время хода (конечно, $$$e_i$$$ для этого цвета не должно быть равно $$$0$$$).

Не забывайте сбрасывать буфер вывода каждый раз, когда что-то выводите!

Примеры
Входные данные
5
1 1 1 1
0
1
1
Выходные данные
1
1 1 1 1
1
Входные данные
4
1 2 3
0
0 1 0
0
1 1 0
0
1 0 1
1
Выходные данные
3
3 1 2
2
1
3
Входные данные
3
1 2
0
1 1
1
Выходные данные
2
1 2
1
Примечание

В первом примере каждая вершина от $$$2$$$ до $$$n$$$ соединена с корнем. Поэтому мы можем покрасить все ребра в один цвет $$$1$$$, и когда игра начнется, будет только одно ребро, инцидентное текущей вершине (и оно будет вести к корню).

Во втором примере дерево представляет собой путь из $$$4$$$ вершин. Мы должны покрасить его ребра в разные цвета, потому что можно показать, что у нас нет выигрышной стратегии с двумя цветами.