Задача №113940. Петербург?
Пытаясь спастись от мира спортивного программирования, Алина сбежала на вокзал и уехала прочь на ночной электричке. Минуты медленно уплывали в даль, и уставшую девочку клонило в сон. Ей снился город-сказка, где не надо программировать, а можно гулять, мечтать и наслаждаться жизнью. Внезапно дождь из интерактивных задач разрушил эту идиллию.
Проснувшись и открыв окно, Алина задалась вопросом весьма философского свойства: «Где я?». С перрона потерявшейся девочке сообщили, что этот город, не похожий ни на что вокруг, представляет собой неориентированный граф на \(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.
Подзадача 0. Тесты из условия
Подзадача 1. (27 баллов) \(N, M \leq 10\). Пройдена подзадача 0.
Подзадача 2. (30 баллов) \(N \leq 10000, M \leq 20000\). Пройдена подзадача 1.
Подзадача 3. (1 балл за каждый пройденный тест) Нет дополнительных ограничений. Пройдена подзадача 2.
В условии в примере взаимодействия вводимые и выводимые данные расположены для удобства восприятия в хронологическом порядке, при реальном взаимодействии никакие «лишние» переводы строк возникать не должны.
Ввод-вывод в примерах демонстрирует пример взаимодействия вашей программы с проверяющей системой.
В первом примере был загадан граф на трех вершинах с ребрами \((1, 2)\), \((2, 3)\) и \((3, 1)\).
Во втором примере была загадан граф на четырех вершинах с ребрами \((1, 2)\), \((2, 3)\), \((3, 4)\) и \((2, 3)\).
Ребро, соединяющее вершины \(u\) и \(v\), называется мостом, если после его удаления между вершинами \(u\) и \(v\) не существует пути.
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