Пытаясь спастись от мира спортивного программирования, Алина сбежала на вокзал и уехала прочь на ночной электричке. Минуты медленно уплывали в даль, и уставшую девочку клонило в сон. Ей снился город-сказка, где не надо программировать, а можно гулять, мечтать и наслаждаться жизнью. Внезапно дождь из интерактивных задач разрушил эту идиллию.
Проснувшись и открыв окно, Алина задалась вопросом весьма философского свойства: «Где я?». С перрона потерявшейся девочке сообщили, что этот город, не похожий ни на что вокруг, представляет собой неориентированный граф на $$$n$$$ вершинах и $$$m$$$ ребрах. Сeй невероятный факт, однако, нисколько не удивил Алину. Она давно мечтала побывать в одном таком городе — Петербурге. Его уникальной отличительной особенностью является то, что хотя бы половина его ребер — мосты (определение дано в конце условия). Так как никакие другие города Алине не интересны, она решила ограничиться расспросом находящихся на платформе эрудированных путешественников. Любой из их них может по данной вершине $$$v$$$ сообщить любое ещё не названное ребро, исходящее из нее, или же заявить об отсутствии таковых.
Алина неуверена в своих силах, поэтому попросила вас помочь ей определить, попала ли она в Петербург. Так как её поезд скоро продолжит свой путь, задать больше $$$3n$$$ вопросов не получится.
Обратите внимание, что в графе могут присутствовать петли и кратные ребра.
В первой строке стандартного потока ввода даны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 100\,000$$$) — число вершин и ребер в графе соответственно.
Для того, чтобы узнать очередное ребро, исходящее из $$$u$$$-й вершины ($$$1 \le u \le n$$$), нужно вывести «? $$$u$$$». После этого ваша программа на вход получит целое число $$$v$$$ ($$$-2 \le v \le -1$$$ или $$$1 \le v \le n$$$) — $$$v = a + b - u$$$, если существует ребро $$$ab$$$, которое инцидентно вершине $$$u$$$ и ещё не было названо, $$$-1$$$, если такого ребра не существует и $$$-2$$$, если вы превысили допустимое число запросов. В последнем случае ваша программа должна немедленно завершиться, в ином случае жюри не гарантирует корректность полученного вами вердикта.
Вам разрешается задать не более $$$3n$$$ вопросов.
Чтобы сообщить, что ответ найден, требуется вывести «! Yes» или «! No», в зависимости от того, является ли загаданный граф Петербургом. В случае положительного ответа выведите $$$\lceil\frac{m}{2}\rceil$$$ строк, по два целых числа $$$u_i$$$ и $$$v_i$$$ в каждой ($$$1 \le u_i, v_i \le n$$$), обозначающих, что ребро $$$(u_i, v_i)$$$ является мостом. Любое ребро в приведенном списке должно встречаться не более одного раза (кратные ребра считаются различными).
Запрос на вывод ответа не входит в ограничение на $$$3n$$$ запросов.
Не забывайте сбрасывать буфер после каждого запроса. Например, на языке C++ надо использовать функцию fflush(stdout) или вызов cout.flush(), на Java вызов System.out.flush(), на Pascal flush(output) и stdout.flush() для языка Python.
3 3
$$$ $$$
2
$$$ $$$
2
$$$ $$$
-1
$$$ $$$
3
$$$ $$$
-1
$$$ $$$
-1
$$$ $$$
? 3
$$$ $$$
? 1
$$$ $$$
? 2
$$$ $$$
? 1
$$$ $$$
? 1
$$$ $$$
? 3
$$$ $$$
! No
4 4
$$$ $$$
2
$$$ $$$
3
$$$ $$$
2
$$$ $$$
-1
$$$ $$$
4
$$$ $$$
-1
$$$ $$$
-1
$$$ $$$
-1
$$$ $$$
$$$ $$$
$$$ $$$
$$$ $$$
? 1
$$$ $$$
? 2
$$$ $$$
? 3
$$$ $$$
? 1
$$$ $$$
? 3
$$$ $$$
? 3
$$$ $$$
? 2
$$$ $$$
? 4
$$$ $$$
! Yes
1 2
3 4
В условии в примере взаимодействия вводимые и выводимые данные расположены для удобства восприятия в хронологическом порядке, при реальном взаимодействии никакие «лишние» переводы строк возникать не должны.
Ввод-вывод в примерах демонстрирует пример взаимодействия вашей программы с проверяющей системой.
В первом примере был загадан граф на трех вершинах с ребрами $$$(1, 2)$$$, $$$(2, 3)$$$ и $$$(3, 1)$$$.
Во втором примере была загадан граф на четырех вершинах с ребрами $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(3, 4)$$$ и $$$(2, 3)$$$.
Ребро, соединяющее вершины $$$u$$$ и $$$v$$$, называется мостом, если после его удаления между вершинами $$$u$$$ и $$$v$$$ не существует пути.
