Это интерактивная задача.
Я хочу сыграть с тобой в одну игру...
Мы загадали циклический граф из \(n\) вершин (\(3 \le n \le 10^{18}\)). Циклическим называется неориентированный граф из \(n\) вершин, образующих один цикл. Каждая вершина принадлежит циклу, то есть длина цикла (количество рёбер в нём) равна в точности \(n\). Порядок вершин в цикле — произвольный.
Вы можете делать запросы следующего вида:
- «? a b», где \(1 \le a, b \le 10^{18}\) и \(a \neq b\). В ответ на запрос интерактор выведет в отдельной строке длину случайного из двух путей из вершины \(a\) в вершину \(b\), либо -1, если \(\max(a, b) > n\). Один из двух путей интерактор выбирает равновероятно. Длина пути — это количество рёбер в нём.
Вы победите, если угадаете количество вершин в загаданном цикле (число \(n\)), сделав не больше \(50\) запросов.
Обратите внимание, что интерактор реализован так, что для любой упорядоченной пары \((a, b)\), на запрос «? a b» он всегда возвращает одно и то же значение, независимо от количества таких запросов. Отметим, что на запрос «? b a» интерактор может дать другой ответ.
Вершины в графе расставлены случайно и их позиции заранее фиксированы.
В этой задаче запрещены взломы. Количество тестов у жюри равно \(50\).
Протокол взаимодействия
Вы можете сделать не более \(50\) запросов. Чтобы сделать запрос, выведите в отдельной строке:
- «? a b», где \(1 \le a, b \le 10^{18}\) и \(a \neq b\). В ответ на запрос интерактор выведет в отдельной строке длину случайного простого пути из вершины \(a\) в вершину \(b\) (не путать с путем из \(b\) в \(a\)), либо \(-1\), если \(\max(a, b) > n\). Один из двух путей интерактор выбирает равновероятно.
Если в результате запроса вашей программой будет получено число 0, то это означает, что вердикт для вашего решения уже определён как «Неправильный ответ» (например, вы сделали больше \(50\) запросов или совершили некорректный запрос). В этом случае ваша программа должна немедленно завершить свою работу. В противном случае в этом сценарии вы можете получить случайный вердикт «Ошибка исполнения», «Превышено ограничение времени» или какой-то другой вместо вердикта «Неправильный ответ».
Ответ, как и запросы, выведите в отдельной строке. Вывод ответа не считается запросом при подсчёте их количества. Чтобы вывести его, используйте следующий формат:
- «! n»: предполагаемую длину загаданного цикла (\(3 \le n \le 10^{18}\)).
После этого ваша программа должна завершить работу.
После вывода очередного запроса обязательно используйте функции очистки потока, чтобы часть вашего вывода не осталась в каком-нибудь буфере. Например, на С++ надо использовать функцию fflush(stdout), на Java вызов System.out.flush(), на Pascal flush(output) и stdout.flush() для языка Python.
Обратите внимание, что интерактор реализован так, что для любой упорядоченной пары \((a, b)\), на запрос «? a b» он всегда возвращает одно и то же значение, независимо от количества таких запросов. Отметим, что на запрос «? b a» интерактор может дать другой ответ.
Вершины в графе расставлены случайно и их позиции заранее фиксированы.
В этой задаче запрещены взломы. Количество тестов у жюри равно \(50\).