|
Темы:
Интерактивные задачи
Мосты
Алгоритмы на графах
– Это что за остановка – Бологое иль Поповка? – А с платформы говорят: – Это город Ленинград.
«Вот какой рассеянный», Самуил Маршак
Пытаясь спастись от мира спортивного программирования, Алина сбежала на вокзал и уехала прочь на ночной электричке. Минуты медленно уплывали в даль, и уставшую девочку клонило в сон. Ей снился город-сказка, где не надо программировать, а можно гулять, мечтать и наслаждаться жизнью. Внезапно дождь из интерактивных задач разрушил эту идиллию.
Проснувшись и открыв окно, Алина задалась вопросом весьма философского свойства: «Где я?». С перрона потерявшейся девочке сообщили, что этот город, не похожий ни на что вокруг, представляет собой неориентированный граф на n вершинах и m ребрах. Сeй невероятный факт, однако, нисколько не удивил Алину. Она давно мечтала побывать в одном таком городе — Петербурге. Его уникальной отличительной особенностью является то, что хотя бы половина его ребер — мосты (определение дано в конце условия). Так как никакие другие города Алине не интересны, она решила ограничиться расспросом находящихся на платформе эрудированных путешественников. Любой из их них может по данной вершине v сообщить любое ещё не названное ребро, исходящее из нее, или же заявить об отсутствии таковых.
Алина неуверена в своих силах, поэтому попросила вас помочь ей определить, попала ли она в Петербург. Так как её поезд скоро продолжит свой путь, задать больше 3n вопросов не получится.
Обратите внимание, что в графе могут присутствовать петли и кратные ребра.
Протокол взаимодействия
В первой строке стандартного потока ввода даны два целых числа n и m (1 ≤ n, m ≤ 100000 ) — число вершин и ребер в графе соответственно.
Для того, чтобы узнать очередное ребро, исходящее из u-й вершины (1 ≤ u ≤ n), нужно вывести « ? u ». После этого ваша программа на вход получит целое число v (−2 ≤ v ≤ −1 или 1 ≤ v ≤ n) — v=a+b−u, если существует ребро ab, которое инцидентно вершине u и ещё не было названо , −1, если такого ребра не существует и −2, если вы превысили допустимое число запросов. В последнем случае ваша программа должна немедленно завершиться, в ином случае жюри не гарантирует корректность полученного вами вердикта.
Вам разрешается задать не более 3n вопросов.
Чтобы сообщить, что ответ найден, требуется вывести « ! Yes » или « ! No », в зависимости от того, является ли загаданный граф Петербургом. В случае положительного ответа выведите \( {m \over 2}\) строк, по два целых числа ui и vi в каждой (1 ≤ ui, vi ≤ n), обозначающих, что ребро (ui, vi) является мостом. Любое ребро в приведенном списке должно встречаться не более одного раза (кратные ребра считаются различными).
Запрос на вывод ответа не входит в ограничение на 3n запросов.
Примечание
В условии в примере взаимодействия вводимые и выводимые данные расположены для удобства восприятия в хронологическом порядке, при реальном взаимодействии никакие «лишние» переводы строк возникать не должны.
Ввод-вывод в примерах демонстрирует пример взаимодействия вашей программы с проверяющей системой.
В первом примере был загадан граф на трех вершинах с ребрами (1, 2) , (2, 3) и (3, 1) .
Во втором примере была загадан граф на четырех вершинах с ребрами (1, 2) , (2, 3) , (3, 4) и (2, 3) .
Ребро, соединяющее вершины u и v, называется мостом, если после его удаления между вершинами u и v не существует пути.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 3
2
2
-1
3
-1
-1 |
? 3
? 1
? 2
? 1
? 1
? 3
! No |
| 2 |
4 4
2
3
2
-1
4
-1
-1
-1 |
? 1
? 2
? 3
? 1
? 3
? 3
? 2
? 4
! Yes
1 2
3 4 |
| |
![]()
|