Codeforces Round 866 (Div. 1) |
---|
Закончено |
Это интерактивная задача.
Как хорошо известно, в городе «E» за его полутора тысячелетнюю историю ни разу не ремонтировали дороги. И только недавно руководство города отремонтировало некоторые из них.
Известно, что всего в городе «E» есть $$$n$$$ перекрестков и $$$m$$$ дорог, пронумерованных целыми числами от $$$1$$$ до $$$m$$$, перемещаться по которым можно в обе стороны. $$$i$$$-я дорога соединяет перекрестки с номерами $$$a_i$$$ и $$$b_i$$$.
Среди всех $$$m$$$ дорог было отремонтировано некоторое подмножество дорог, но вам не известно, какое именно. Единственная информация, которую вы смогли получить от дорожных служб города, это то, что от любого перекрестка можно доехать до любого другого, двигаясь только по отремонтированным дорогам.
Вы — молодой предприниматель, и решили организовать службу доставки свежего сырого мяса в городе «E» (в самом городе такое мясо называют «стейками», оно пользуется большой популярностью у местных жителей). Вы уже набрали штат курьеров, однако курьеры готовы перемещаться только по отремонтированным дорогам. Теперь вам предстоит выяснить, какие дороги уже отремонтированы.
Городская администрация предоставила вам город на некоторое время, поэтому вы можете делать различные действия одного из трех типов:
К сожалению, город предоставлен в ваше полное распоряжение ненадолго, поэтому вы можете сделать не более $$$100 \cdot m$$$ запросов.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 1\,000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка содержит каждого наборе входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2\,000$$$, $$$n - 1 \le m \le 2\,000$$$) — число перекрестков и дорог в городе «E».
Каждая из следующих $$$m$$$ строк содержит описание одной дороги. $$$i$$$-я из этих строк содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — концы $$$i$$$-й дороги. Гарантируется, что никакая дорога не соединяет город сам с собой, при этом возможно, что между парой различных перекрестков есть несколько дорог.
Гарантируется, что сумма $$$n$$$ и сумма $$$m$$$ по всем наборам входных данных не превосходит $$$2\,000$$$.
После того, как вы считали описание набора входных данных, вы можете задавать запросы. Запросы могут быть трех типов:
Всего вы можете задать не более $$$100 \cdot m$$$ запросов для каждого набора входных данных.
После того, как вы нашли все отремонтированные дороги, выведите «! $$$c_1,\ c_2,\ c_3,\ \ldots,\ c_m$$$», где $$$c_i$$$ равно $$$1$$$, если дорога $$$i$$$ отремонтирована, и $$$0$$$, если дорога не отремонтирована. Этот вывод не будет считаться в общем числе запросов. На это программа жюри выведет $$$1$$$, если ваш ответ правильный, и $$$0$$$, если ответ не правильный. Если вы считали $$$0$$$, то ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока. Если вы считали $$$1$$$, то перейдите к следующему набору входных данных, или завершите программу, если такого нет.
Обратите внимание, что вам не обязательно разблокировать все дороги на момент вывода ответа. Гарантируется, что все отремонтированные дороги зафиксированы изначально и не будут меняться программой жюри в зависимости от запросов.
После вывода запроса или ответа не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
Взломы
Вы не можете делать взломы по этой задаче.
2 2 2 1 2 2 1 1 0 1 1 3 3 1 2 2 3 3 1 1 1 1 0 1 1 1 1
- 1 ? 1 ? 2 - 2 + 1 ? 1 ! 1 0 - 1 ? 2 ? 1 - 2 ? 3 ? 3 + 1 ? 3 ? 2 ? 1 ! 1 1 1
В первом наборе входных данных дорога $$$1$$$ отремонтирована, а дорога $$$2$$$ — нет. Для первого запроса доставки в качестве $$$s$$$ был выбран перекресток $$$1$$$, поэтому путь от перекрестка $$$1$$$ до $$$1$$$ есть. Для второго запроса доставки в качестве $$$s$$$ был выбран перекресток $$$1$$$, так как в города заблокирована единственная отремонтированная дорога, то пути между перекрестками $$$1$$$ и $$$2$$$ нет. Для третьего запроса доставки в качестве $$$s$$$ был выбран перекресток $$$2$$$, путь между перекрестками $$$2$$$ и $$$1$$$ есть по дороге $$$1$$$, которая отремонтирована и разблокирована.
Во втором наборе входных данных для запросов доставки в качестве стартовых перекрестков были выбраны перекрестки $$$1$$$, $$$3$$$, $$$1$$$, $$$2$$$, $$$2$$$, $$$3$$$, $$$1$$$.
Название |
---|