Это интерактивная задача. Не забывайте о том, что ваша программа должна каждый раз после вывода запроса сбрасывать буфер вывода. Для сброса буфера вывода можно использовать fflush(stdout) в C++, system.out.flush() в Java, stdout.flush() в Python или flush(output) в Pascal. Если вы используете другой язык программирования, посмотрите в его документации, как выполняется эта операция. Также рекомендуем вам прочесть руководство по интерактивным задачам: https://codeforces.net/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$$$-й вершины в дереве.
Сначала вы должны вывести выбранную вами раскраску ребер следующим образом:
Затем начинается игра. В начале каждого хода программа жюри выводит что-то одно из следующего:
Если вы получаете $$$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$$$ вершин. Мы должны покрасить его ребра в разные цвета, потому что можно показать, что у нас нет выигрышной стратегии с двумя цветами.
Название |
---|