E. Дороги в городе E
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача.

Как хорошо известно, в городе «E» за его полутора тысячелетнюю историю ни разу не ремонтировали дороги. И только недавно руководство города отремонтировало некоторые из них.

Известно, что всего в городе «E» есть $$$n$$$ перекрестков и $$$m$$$ дорог, пронумерованных целыми числами от $$$1$$$ до $$$m$$$, перемещаться по которым можно в обе стороны. $$$i$$$-я дорога соединяет перекрестки с номерами $$$a_i$$$ и $$$b_i$$$.

Среди всех $$$m$$$ дорог было отремонтировано некоторое подмножество дорог, но вам не известно, какое именно. Единственная информация, которую вы смогли получить от дорожных служб города, это то, что от любого перекрестка можно доехать до любого другого, двигаясь только по отремонтированным дорогам.

Вы — молодой предприниматель, и решили организовать службу доставки свежего сырого мяса в городе «E» (в самом городе такое мясо называют «стейками», оно пользуется большой популярностью у местных жителей). Вы уже набрали штат курьеров, однако курьеры готовы перемещаться только по отремонтированным дорогам. Теперь вам предстоит выяснить, какие дороги уже отремонтированы.

Городская администрация предоставила вам город на некоторое время, поэтому вы можете делать различные действия одного из трех типов:

  1. Заблокировать дорогу с номером $$$x$$$. В этом случае перемещение по дороге для курьеров будет запрещено. Исходно все дороги разблокированы.
  2. Разблокировать дорогу с номером $$$x$$$. В этом случае курьеры смогут двигаться по дороге $$$x$$$, если она отремонтирована.
  3. Попробовать доставить заказ на перекресток с номером $$$y$$$. В этом случае один из ваших курьеров начнет двигаться с неизвестного вам перекрестка $$$s$$$ и доставит заказ на перекресток с номером $$$y$$$ в том случае, если существует путь по разблокированным отремонтированным дорогам от перекрестка $$$s$$$ до перекрестка $$$y$$$. При этом гарантируется, что перекресток $$$s$$$ будет выбран заранее.

К сожалению, город предоставлен в ваше полное распоряжение ненадолго, поэтому вы можете сделать не более $$$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$$$.

Протокол взаимодействия

После того, как вы считали описание набора входных данных, вы можете задавать запросы. Запросы могут быть трех типов:

  1. «- $$$x$$$» ($$$1 \le x \le m$$$). В этом случае дорога с номером $$$x$$$ блокируется, если она ещё не была заблокирована.
  2. «+ $$$x$$$» ($$$1 \le x \le m$$$). В этом случае дорога с номером $$$x$$$ разблокируется. Обратите внимание, что дорога $$$x$$$ должна быть заранее заблокирована. Исходно все дороги разблокированы.
  3. «? $$$y$$$» ($$$1 \le y \le n$$$). В этом случае программа жюри выбирает некоторый город $$$s$$$. В случае, если от города $$$s$$$ до города $$$y$$$ можно добраться по разблокированным отремонтированным дорогам, программа жюри выведет $$$1$$$, иначе программа жюри выведет $$$0$$$. Обратите внимание, что город $$$s$$$ будет выбран до получения информации о городе $$$y$$$, однако при выборе города $$$s$$$ могут учитываться ваши предыдущие запросы.

Всего вы можете задать не более $$$100 \cdot m$$$ запросов для каждого набора входных данных.

После того, как вы нашли все отремонтированные дороги, выведите «! $$$c_1,\ c_2,\ c_3,\ \ldots,\ c_m$$$», где $$$c_i$$$ равно $$$1$$$, если дорога $$$i$$$ отремонтирована, и $$$0$$$, если дорога не отремонтирована. Этот вывод не будет считаться в общем числе запросов. На это программа жюри выведет $$$1$$$, если ваш ответ правильный, и $$$0$$$, если ответ не правильный. Если вы считали $$$0$$$, то ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока. Если вы считали $$$1$$$, то перейдите к следующему набору входных данных, или завершите программу, если такого нет.

Обратите внимание, что вам не обязательно разблокировать все дороги на момент вывода ответа. Гарантируется, что все отремонтированные дороги зафиксированы изначально и не будут меняться программой жюри в зависимости от запросов.

После вывода запроса или ответа не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Взломы

Вы не можете делать взломы по этой задаче.

Пример
Входные данные
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$$$.