Це багатопрохідна інтерактивна задача. Не забувайте очищувати буфер виводу після кожного друку. Для очищення буфера виводу можна використовувати:
fflush(stdout)абоcout.flush()у C/C++;System.out.flush()у Java та Kotlin;sys.stdout.flush()у Python.
Концепція гри, проілюстрована ChatGPT.
У класичній грі онлайн-парування (online matching) ребра графа відкриваються одне за одним. Щоразу, коли показують ребро, ви повинні негайно й безповоротно вирішити, чи включати його до свого парування. Ваша мета — гарантувати, що жодні два вибрані ребра не мають спільної вершини, водночас максимізуючи загальну кількість вибраних ребер.
Ви — амбітний науковець у галузі комп'ютерних наук, спраглий слави. Як вам добре відомо, знайти максимальне парування в онлайн-режимі з високою ймовірністю доведено неможливо — навіть для найпростіших класів графів, таких як двочасткові графи. Та там, де інші бачать фундаментальний бар'єр, ви бачите шанс на славу. Сьогодні ви заявляєте, що розв'язали давню відкриту проблему для дерев, і готові представити світові свій революційний алгоритм.
Є лише одна проблема: вчора ви виявили помилку у своєму доведенні й досі не уявляєте, як її виправити. Не бажаючи сходити зі сцени, ви вирішуєте перетворити свою демонстрацію на магічне шоу — ваш асистент, схований за лаштунками, перед початком гри передасть невеличку підказку про все дерево з $n$ вершинами.
Ваш початковий план був простим: нехай асистент напряму передає відповідь для кожного запиту ребра. Для цього ви встановили таємний навушник, здатний прийняти один двійковий рядок довжини $(n - 1)$. Але публіка скептично ставиться до вашого «прориву». Щоб унеможливити будь-які заздалегідь домовлені хитрощі, глядачі вимагають, щоб ребра подавалися в рівноймовірно випадковому порядку — такому, який ні ви, ні ваш асистент не можете передбачити чи контролювати.
Сцену підготовлено. Софіти спрямовані на вас. Тепер доведіть своє твердження — не перемикаючи канал.
Протокол взаємодії
Ваш розв'язок запускається двічі на кожному тесті. У раунді prepare ваш розв'язок грає роль асистента. У раунді play ваш розв'язок грає роль вас, ілюзіоніста. В обох раундах ваш розв'язок оцінюється як інтерактивна процедура.
Раунд підготовки (Prepare Round)
Перший рядок вхідних даних містить слово 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 Round)
Ваш розв'язок буде перезапущено для раунду 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$ тестів, не враховуючи прикладів. Щоб здати задачу, ваш розв'язок має бути правильним на всіх тестах, включно з прикладами.
Гарантується, що всі випадкові перестановки фіксуються до отримання виводу розв'язку. Випадковість фіксована для кожного тесту шляхом фіксації зерна (seed) генератора псевдовипадкових чисел.
Для допомоги в розробці та тестуванні вашого розв'язку надається інструмент тестування.
Приклад
Приклад 1, Прохід 1
Вхідні дані
prepare 3 1 2 1 3
Вихідні дані
00
Приклад 1, Прохід 2
Вхідні дані
play 3 00 1 3 1 2
Вихідні дані
take ignore
Пояснення до прикладу 1
Оскільки $|M^*| = 1$, взяття будь-якого одного ребра є прийнятним, а підказка може бути довільною.