Задача . E. Интерактивная игра с раскраской

Это интерактивная задача. Не забывайте о том, что ваша программа должна каждый раз после вывода запроса сбрасывать буфер вывода. Для сброса буфера вывода можно использовать fflush(stdout) в C++, system.out.flush() в Java, stdout.flush() в Python или flush(output) в Pascal. Если вы используете другой язык программирования, посмотрите в его документации, как выполняется эта операция. Также рекомендуем вам прочесть руководство по интерактивным задачам: https://cf.m27.workers.dev/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\)).

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