Задача . E. Pink Floyd

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

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

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

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

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

Чтобы узнать направление зеленого ребра между вершинами \(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)\) должны быть различны и не должны совпадать с теми же парами для рёбер розового цвета.