E. Pink Floyd
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Учёные находятся всего в нескольких шагах от открытия новой оптимизации алгоритма Флойда, позволяющей ему работать за линейное время! Осталась лишь одна часть.

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

Для оптимизации Флойда выбраны $$$m$$$ рёбер и покрашены в розовый цвет, остальные ребра покрашены в зеленый. Вы знаете направление каждого из этих $$$m$$$ ребер, однако, направление зеленых рёбер вам заранее неизвестно. За один запрос вы можете узнать направление одного зеленого ребра, но всего вы можете сделать не более $$$2 \cdot n$$$ запросов.

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

Входные данные

В первой строке находятся два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 100\,000$$$, $$$0 \le m \le 100\,000$$$) — число вершин и число рёбер розового цвета.

В $$$i$$$-й из следующих $$$m$$$ строках находятся два целых числа $$$u_i$$$, $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — начало $$$i$$$-го ребра розового цвета и его конец. Гарантируется, что все неупорядоченные пары $$$(u_i, v_i)$$$ различны.

Выходные данные

Когда вы найдете ответ, выведите «!» и номер вершины, от которой каждая другая достижима по одноцветному пути.

Протокол взаимодействия

Чтобы узнать направление зеленого ребра между вершинами $$$a$$$ и $$$b$$$, в одной строке через пробел выведите символ «?», а затем два целых числа $$$a$$$ и $$$b$$$.

В ответ на это считайте целое число, которое будет равно $$$1$$$, если ребро направленно от $$$a$$$ к $$$b$$$, и $$$0$$$, если ребро направлено от $$$b$$$ к $$$a$$$.

Вы можете задать не более $$$2 \cdot n$$$ вопросов, в противном случае вы получите вердикт Wrong Answer.

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Ответ $$$-1$$$ вместо $$$0$$$ или $$$1$$$ означает, что ваша программа сделала некорректный запрос или превысила число запросов. Ваша программа должна немедленно завершиться после прочтения ответа $$$-1$$$, вы получите вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.

Взломы

Для взлома задайте тест в следующем формате. В первой строке должны находиться два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 300$$$, $$$0 \le m \le n \cdot (n - 1) / 2$$$) — число вершин и число рёбер розового цвета.

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

В $$$i$$$-й из следующих $$$(n \cdot (n - 1) / 2 - m)$$$ строках должны находиться два целых числа $$$a_i$$$, $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$)), означающих, что есть ребро зеленого цвета от вершины $$$a_i$$$ к вершине $$$b_i$$$. Все неориентированные пары $$$(a_i, b_i)$$$ должны быть различны и не должны совпадать с теми же парами для рёбер розового цвета.

Пример
Входные данные
4 2
1 2
3 4
0
1
1
Выходные данные
? 1 3
? 4 2
? 3 2
! 3
Примечание

В приведённом примере ответ на запрос «? 1 3» — 0, поэтому ребро ориентированно от 3 к 1; ответ на запрос «? 4 2» — 1, поэтому ребро ориентированно от 4 к 2; ответ на запрос «? 3 2» — 1, поэтому ребро ориентированно от 3 к 2. Тогда от вершины 3 есть пути по зелёным рёбрам к вершинам 1 и 2, а так же есть путь по розовым рёбрам до вершины 4.