Это многопроходная интерактивная задача. Не забывайте очищать буфер вывода после каждого вывода данных. Для очистки буфера можно использовать:
fflush(stdout)илиcout.flush()в C/C++;System.out.flush()в Java и Kotlin;sys.stdout.flush()в Python.
В классической игре онлайн-паросочетания ребра графа открываются по одному. Каждый раз, когда ребро показано, вы должны немедленно и окончательно решить, включить ли его в свое паросочетание. Ваша цель — гарантировать, что никакие два выбранных ребра не имеют общую вершину, при этом максимизируя общее количество выбранных ребер.
Вы амбициозный ученый-компьютерщик, жаждущий славы. Как вы хорошо знаете, нахождение максимального паросочетания в онлайн-режиме доказуемо невозможно с высокой вероятностью — даже для простейших классов графов, таких как двудольные графы. Однако там, где другие видят фундаментальный барьер, вы видите возможность для славы. Сегодня вы утверждаете, что решили давнюю открытую проблему для деревьев, и готовы представить миру свой революционный алгоритм.
Есть только одна проблема: вчера вы обнаружили ошибку в своем доказательстве и до сих пор понятия не имеете, как ее исправить. Не желая покидать центр внимания, вы решаете превратить свою демонстрацию в магическое шоу — ваш помощник, скрытый за кулисами, передаст небольшую подсказку обо всем дереве с $n$ вершинами до начала игры.
Ваш первоначальный план был прост: пусть ваш помощник отправляет ответ на каждый запрос ребра напрямую. Для этого вы установили секретный наушник, способный принимать одну бинарную строку длины $(n - 1)$. Но аудитория скептически относится к вашему «прорыву». Чтобы предотвратить любые заранее подготовленные уловки, они требуют, чтобы ребра предъявлялись в равномерно случайном порядке — таком, который ни вы, ни ваш помощник не можете предсказать или контролировать.
Сцена готова. Огни направлены на вас. Теперь докажите свое утверждение — не меняя канала.
Протокол взаимодействия
Ваше решение выполняется дважды на каждом тесте. В раунде prepare ваше решение будет выступать в роли помощника. В раунде play ваше решение будет выступать в роли вас, фокусника. В обоих раундах ваше решение будет оцениваться как интерактивная процедура.
Раунд Prepare
Первая строка входных данных содержит слово prepare. Вторая строка содержит целое число $n$ ($2 \le n \le 500$) — количество вершин. Следующие $(n - 1)$ строк содержат по два целых числа $u$ и $v$ ($1 \le u, v \le n, u < v$), обозначающих неориентированное ребро между $u$ и $v$ в дереве.
Вы должны вывести одну строку, содержащую бинарную строку $s$ длиной ровно $(n - 1)$, состоящую только из символов 0 и 1. Это строка, передаваемая во второй раунд play. Если ваш вывод не соответствует требуемому формату, вы получите вердикт Wrong Answer.
Раунд Play
Ваше решение будет перезапущено для раунда play.
Первая строка содержит слово play. Вторая строка содержит целое число $n$. Третья строка содержит бинарную строку $s$, в точности такую, которую вы вывели в раунде prepare.
После этого игра начинается с $(n - 1)$ ходов. На каждом ходу предоставляется строка, содержащая два целых числа $u$ и $v$ ($1 \le u, v \le n, u < v$). В качестве ответа вы должны вывести одну строку, содержащую либо take, либо ignore. Все ребра в первом раунде будут предоставлены ровно один раз, а порядок ребер выбирается равномерно случайным образом из $(n - 1)!$ возможных перестановок.
Если вывод имеет неверный формат, игра немедленно завершится без дополнительной информации от интерактора.
Оценка правильности
Пусть $M$ — множество ребер, которые выбрало ваше решение. Считается приемлемым, если ни одна вершина не инцидентна более чем одному выбранному ребру и $|M| = |M^*|$, где $M^*$ — максимальное паросочетание графа.
Существует ровно 50 тестов, исключая примеры. Чтобы пройти задачу, ваше решение должно быть правильным на всех тестах, включая примеры.
Все перестановки гарантированно фиксируются до получения вывода решения. Случайность фиксируется для каждого теста путем фиксации начального значения генератора псевдослучайных чисел.
Для помощи в разработке и тестировании вашего решения предоставляется инструмент тестирования.
Примеры
Пример 1, Раунд 1
prepare 3 1 2 1 3
00
Пример 1, Раунд 2
play 3 00 1 3
take
1 2
ignore
Примечание
Пояснение к примеру 1: Так как $|M^*| = 1$, выбор любого ребра является приемлемым, и подсказка может быть произвольной.
Figure 1. Magically Marked Matching Master