Это интерактивная задача с двойным запуском (коммуникационная), в которой взаимодействие происходит дважды.
Есть два игрока: Игрок A (Neri) и Игрок B (Mashiro). Жюри сначала взаимодействует с Игроком A. После завершения взаимодействия с Игроком A жюри взаимодействует с Игроком B. Обратите внимание, что Игрок A и Игрок B не могут напрямую передавать информацию друг другу; оба игрока могут только отправлять информацию жюри или получать информацию от жюри, но они могут заранее договориться о стратегии общения.
Перед началом взаимодействия жюри задаёт неориентированное дерево $$$T$$$ размера $$$n$$$ и целое число $$$s$$$ ($$$1\le s\le 2^{n-1}$$$). Эти значения одинаковы для обоих игроков.
Игрок A (Neri) сначала получает от жюри два целых числа $$$n$$$ и $$$s$$$, не получая дополнительной информации о дереве $$$T$$$. Затем жюри будет взаимодействовать с Neri ровно $$$n-1$$$ раундов. В каждом раунде взаимодействия:
- Жюри раскрывает Neri одно неориентированное ребро дерева $$$T$$$, после чего Neri должен немедленно задать ему направление.
Обратите внимание, что после этого взаимодействия все $$$n-1$$$ рёбер дерева $$$T$$$ будут ориентированы, образуя новое ориентированное дерево $$$T'$$$.
Игрок B (Mashiro) получает ориентированное дерево $$$T'$$$, созданное во время взаимодействия между Neri и жюри. Её задача — определить значение $$$s$$$ по полученной информации.
Neri хочет гарантировать, что Mashiro сможет определить целое число $$$s$$$. Ваша задача — действовать как оба игрока и определить оптимальную стратегию взаимодействия для обоих игроков так, чтобы Mashiro смогла правильно определить целое число $$$s$$$.
Первый запуск
Ваш код будет запущен ровно два раза для каждого набора входных данных. При первом запуске вы будете Игроком A (Neri).
Ввод
Первая строка ввода содержит два целых числа $$$t$$$ и $$$q$$$ ($$$1 \le t \le 10^4$$$, $$$q=1$$$) — количество наборов входных данных и номер запуска. Здесь параметр $$$q=1$$$ нужен для того, чтобы ваша программа поняла, что это её первый запуск, и должна действовать как Игрок A (Neri).
Для каждого набора входных данных сначала нужно прочитать два целых числа $$$n$$$ и $$$s$$$ ($$$3\le n \le 30$$$, $$$1\le s \le 2^{n-1}$$$) — размер $$$T$$$ и передаваемое число.
Взаимодействие
Для каждого набора входных данных, как уже было сказано, сначала вы получите $$$n$$$ и $$$s$$$ во входных данных от жюри согласно формату выше. Затем вам нужно ровно $$$n-1$$$ раз взаимодействовать с жюри:
- Сначала прочитайте от жюри два целых числа $$$u$$$ и $$$v$$$ ($$$1\le u \lt v\le n$$$), обозначающие, что в $$$T$$$ есть неориентированное ребро $$$(u,v)$$$;
- Затем выведите жюри две целые числа $$$a$$$ и $$$b$$$ в новой строке, разделённые пробелом, где $$$(a,b)$$$ — это либо $$$(u,v)$$$, либо $$$(v,u)$$$. Если вы выводите $$$(a,b)=(u,v)$$$, это означает, что вы задаёте направление $$$u\rightarrow v$$$, а если вы выводите $$$(a,b)=(v,u)$$$, это означает, что вы задаёте направление $$$v\rightarrow u$$$.
Обратите внимание, что вы должны задать направление для текущего неориентированного ребра до получения информации о следующем.
После этого вы либо переходите к следующему набору входных данных, либо ваша программа должна завершиться, если вы обработали все наборы входных данных.
Интерактор не адаптивный, то есть дерево $$$T$$$ в каждом наборе входных данных фиксируется до начала любого взаимодействия.
После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».
На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.
Второй запуск
При втором запуске вы являетесь Игроком B (Mashiro).
Ввод
Первая строка ввода содержит два целых числа $$$t$$$ и $$$q$$$ ($$$1 \le t \le 10^4$$$, $$$q=2$$$) — количество наборов входных данных и номер запуска. Здесь параметр $$$q=2$$$ нужен для того, чтобы ваша программа поняла, что это её второй запуск, и должна действовать как Игрок B (Mashiro).
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3\le n \le 30$$$) — размер $$$T'$$$.
Затем следуют $$$n-1$$$ строк, каждая из которых содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1\le u,v\le n$$$), обозначающие, что в $$$T'$$$ есть ориентированное ребро $$$u\rightarrow v$$$.
Обратите внимание, что наборы входных данных во втором запуске могут быть перемешаны. Обратитесь к примерам взаимодействия для наглядности.
Вывод
Для каждого набора входных данных выведите одно целое число $$$s$$$ — число, которое вы определили по $$$T'$$$.
После этого не забудьте вывести перевод строки и сбросить буфер вывода. Иначе вы получите вердикт Решение «зависло». Затем переходите к следующему набору входных данных или завершайте программу, если это последний набор.
Взломы
Взломы в этой задаче отключены.
$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:
- fflush(stdout) или cout.flush() в C++;
- sys.stdout.flush() в Python;
- смотрите документацию для других языков.
2 17 211 63 52 43 41 26 79 591 21 43 43 53 85 66 78 9
6 1 3 5 4 2 3 4 1 2 7 6 1 2 1 4 3 4 3 5 8 3 5 6 6 7 9 8
2 2 9 8 3 9 8 1 4 3 4 1 2 5 6 6 7 3 5 7 3 4 1 2 7 6 6 1 3 5 4 2
59 21
Для первого запуска: Целые числа $$$s$$$, переданные Neri, равны соответственно $$$s=21$$$ и $$$s=59$$$. Затем, согласно некоторой стратегии, согласованной между игроками, Neri ориентировал деревья.
Для второго запуска: Обратите внимание, что наборы входных данных переупорядочены между запусками. Ниже приведены иллюстрации $$$T'$$$ для обоих наборов входных данных в порядке второго запуска:
Иллюстрация для первого набора входных данных 
Иллюстрация для второго набора входных данных Инструмент тестирования
Для локального тестирования вам предоставлен командный инструмент. Вы можете скачать его из материалов.
Чтобы использовать инструмент, вам нужен установленный Python. Выполните в терминале команду ниже:
- В Windows: python treedir_testing_tool.py [–quiet] <data_file> <program> <arguments>
- В Linux: python3 treedir_testing_tool.py [–quiet] <data_file> <program> <arguments>
Пояснение к аргументам:
- -q, –quiet — необязательный аргумент. Инструмент будет печатать журналы взаимодействия между собой и вашей программой, а при включении этого флага перестанет их печатать.
- data_file — входной файл, который вы передаёте инструменту. Он должен иметь формат ниже:
- Первая строка содержит два целых числа $$$t$$$ и $$$\text{seed}$$$ — количество наборов входных данных и seed для перемешивания порядка наборов входных данных/рёбер. Если задать $$$\text{seed}=0$$$, инструмент сохранит порядок без перемешивания.
- Для каждого набора входных данных первая строка содержит два целых числа $$$n$$$ и $$$s$$$. В следующих $$$n-1$$$ строках каждая строка содержит два целых числа $$$u$$$ и $$$v$$$, задающие ребро в $$$T$$$.
- program — имя вашей скомпилированной программы.
- arguments — аргументы, необходимые вашей программе.
Комментарии в начале программы содержат подробную информацию об инструменте (на английском).
Обратите внимание, что:
- Этот инструмент не совсем такой же, как интерактор задачи. Вердикты жюри могут отличаться.
- Этот инструмент проверит, что ваш входной файл соответствует формату, но не будет проверять, удовлетворяет ли ваш ввод ограничениям.
- Этот инструмент не будет проверять, укладывается ли ваша программа в ограничения по времени/памяти.
