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

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

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

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

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

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

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

К сожалению, город предоставлен в ваше полное распоряжение не надолго, поэтому вы можете сделать не более $$$100 \cdot m$$$ запросов.

Ваша программа будет взаимодействовать с программой жюри с использованием стандартных потоков ввода и вывода. Каждое взаимодействие будет состоять из решения задачи для нескольких наборов входных данных.

Сначала ваша программа должна считать целое число $$$t$$$ ($$$1 \le t \le 1\,000$$$) — количество наборов входных данных в рамках одного взаимодействия с программой жюри. Затем $$$t$$$ раз необходимо выполнить взаимодействие по решению задачи для набора входных данных.

Рассмотрим протокол взаимодействия для одного набора входных данных.

Сначала ваша программа должна считать данные в следующем формате.

Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2\,000$$$, $$$n - 1 \le m \le 2\,000$$$) — число перекрестков и дорог в Ельце.

Каждая из следующих $$$m$$$ строк содержит описание одной дороги. $$$i$$$-я из этих строк содержит два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$) — номера перекрестков, которые соединяет $$$i$$$-я дорога. Гарантируется, что никакая дорога не соединяет перекресток сам с собой. При этом возможно, что между парой различных перекрестков есть несколько дорог.

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

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

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

Гарантируется, что суммарно по всем наборам входных данных в одном тесте, сумма $$$n$$$ и сумма $$$m$$$ не превосходят $$$2\,000$$$.

Если вы используете «cout « ... « endl» в C++, «System.out.println» в Java, «print» в Python, «writeln» в Pascal, то сброс потока вывода происходит автоматически, дополнительно ничего делать не требуется.

Если вы используете другой способ вывода, рекомендуется делать сброс буфера потока вывода. Обратите внимание, что перевод строки надо выводить в любом случае. Для сброса буфера потока вывода можно использовать «fflush(stdout)» в С++, «flush(output)» в Pascal, «System.out.flush()» в Java, «sys.stdout.flush()» в Python.