Пытаясь спастись от мира спортивного программирования, Алина сбежала на вокзал и уехала прочь на ночной электричке. Минуты медленно уплывали в даль, и уставшую девочку клонило в сон. Ей снился город-сказка, где не надо программировать, а можно гулять, мечтать и наслаждаться жизнью. Внезапно дождь из интерактивных задач разрушил эту идиллию.
Проснувшись и открыв окно, Алина задалась вопросом весьма философского свойства: «Где я?». С перрона потерявшейся девочке сообщили, что этот город, не похожий ни на что вокруг, представляет собой неориентированный граф на \(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
Это интерактивная задача.
В выходной Алексей вместе со своими одноклассниками решил посетить парк аттракционов. Поскольку Алексею очень нравится решать головоломки и получать за это призы, его заинтересовал новый павильон «Угадай-ка!», где посетителям предлагается сыграть в следующую игру.
На столе в павильоне есть клетчатое прямоугольное поле размера \(n \times m\), каждая клетка раскрашена в один из \(k\) разных цветов, и есть колода из \(n \cdot m\) карт с написанными на них числами от 1 до \(n \cdot m\). Ведущий игры в павильоне загадывает одну из карт колоды, а посетитель должен её отгадать. Чтобы отгадать неизвестную ему карту, посетитель задаёт ведущему один или несколько запросов следующим образом:
Всего посетителю разрешено разложить карты и получить ответ ведущего не более \(99\) раз, после чего он должен правильно назвать номер загаданной карты. Гарантируется, что ответы ведущего не противоречивы, то есть всегда существует по крайней мере одна карта, для которой все данные ведущим ответы верны.
Напишите программу, которая поможет Алексею получить приз!
Ваша программа будет общаться с тестирующей системой по протоколу, описанному ниже.
При запуске решения на вход подаются три целых положительных числа \(n\), \(m\) и \(k\) (\(1 \leq n, m \leq 10\), \(2 \leq k \leq n \cdot m\)) — размеры игрового поля и количество цветов, в которые раскрашено поле. В каждой из следующих \(n\) строк передаётся по \(m\) целых чисел через пробел, каждое от \(1\) до \(k\) — раскраска клеток игрового поля. Гарантируется, что для каждого из \(k\) цветов на поле есть по крайней мере одна клетка, раскрашенная в этот цвет.
Вам разрешается задать ведущему не более \(99\) запросов , чтобы угадать загаданную ведущим карту.
Чтобы задать запрос, выведите строку « ? », после чего выведите \(n\) строк по \(m\) целых чисел в каждой — номера карт, раскладываемых вами в соответствующие клетки поля. Каждое число должно быть от 1 до \(n \cdot m\), номера карт не должны повторяться.
В ответ на каждый запрос вводится целое число \(c\) — цвет клетки, в которую вы положили загаданную карту, или число \(-1\) в случае, если программа превысила ограничение по числу запросов. Обратите внимание, в случае считывания числа \(-1\) вы обязательно должны сразу завершить вашу программу. В противном случае, вердикт тестирующей системы может быть некорректным!
Как только вы найдете ответ, выведите строку « Ready! ». В следующей строке выведите целое число \(x\) (\(1 \leq x \leq n \cdot m\)) — номер загаданной ведущим карты. После этого ваша программа должна завершиться.
Для установки правильности вашей программы жюри может запускать её произвольное количество раз для одного и того же игрового поля с разными загаданными картами.
В условии в примере взаимодействия вводимые и выводимые данные расположены для удобства восприятия в хронологическом порядке, при реальном взаимодействии никакие «лишние» переводы строк возникать не должны.
В примере поле 2 на 3 раскрашено в 3 цвета. Ответ на первый запрос — цвет 1, следовательно, ведущий загадал карту c номером \(1\) или с номером \(3\). Ответ на второй запрос — цвет 2, это говорит о том, что ведущий загадал карту с номером \(3\) или \(4\). Следовательно, была загадана карта с номером 3. Обратите внимание, что при проверке вашей программы на этом тесте в тестирующей системе может быть загадана другая карта.
В точности соблюдайте формат выходных данных. После каждого вывода обязательно выводите один перевод строки и сбрасывайте буфер вывода — для этого используйте flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.
2 3 3 1 2 1 2 3 3 1 2
? 1 2 3 4 5 6 ? 2 4 6 3 1 5 Ready! 3