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

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

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

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

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

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

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

• в первой строке выведите одно целое число $$$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$$$).

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