CF1729E.Guess the Cycle Size

This is an interactive problem.

I want to play a game with you...

We hid from you a cyclic graph of $n$ vertices ($3 \le n \le 10^{18}$). A cyclic graph is an undirected graph of $n$ vertices that form one cycle. Each vertex belongs to the cycle, i.e. the length of the cycle (the number of edges in it) is exactly $n$. The order of the vertices in the cycle is arbitrary.

You can make queries in the following way:

• "? a b" where $1 \le a, b \le 10^{18}$ and $a \neq b$. In response to the query, the interactor outputs on a separate line the length of random of two paths from vertex $a$ to vertex $b$, or -1 if $\max(a, b) \gt n$. The interactor chooses one of the two paths with equal probability. The length of the path —is the number of edges in it.

You win if you guess the number of vertices in the hidden graph (number $n$) by making no more than $50$ queries.

Note that the interactor is implemented in such a way that for any ordered pair $(a, b)$, it always returns the same value for query "? a b", no matter how many such queries. Note that the "? b a" query may be answered differently by the interactor.

The vertices in the graph are randomly placed, and their positions are fixed in advance.

Hacks are forbidden in this problem. The number of tests the jury has is $50$.

Interaction

You can make no more than $50$ of queries. To make a query, output on a separate line:

• "? a b", where $1 \le a, b \le 10^{18}$ and $a \neq b$. In response to the query, the interactor will output on a separate line the length of a random simple path from vertex $a$ to vertex $b$ (not to be confused with the path from $b$ to $a$), or $-1$ if $\max(a, b) \gt n$. The interactor chooses one of the two paths with equal probability.

If your program gets a number 0 as a result of a query, it means that the verdict for your solution is already defined as "wrong answer" (for example, you made more than $50$ queries or made an invalid query). In this case, your program should terminate immediately. Otherwise, in this scenario you may get a random verdict "Execution error", "Exceeded time limit" or some other verdict instead of "Wrong answer".

The answer, like queries, print on a separate line. The output of the answer is not counted as a query when counting them. To print it, use the following format:

• "! n": the expected size of the hidden graph ($3 \le n \le 10^{18}$).

After that, your program should terminate.

After the output of the next query, be sure to use stream cleaning functions so that some of your output is not left in some buffer. For example, in C++ you should use function flush(stdout), in Java call System.out.flush(), in Pascal flush(output) and stdout.flush() for Python.

Note that the interactor is implemented in such a way that for any ordered pair $(a, b)$, it always returns the same value for query "? a b", no matter how many such queries. Note that the "? b a" query may be answered differently by the interactor.

The vertices in the graph are randomly placed, and their positions are fixed in advance.

Hacks are forbidden in this problem. The number of tests the jury has is $50$.

这是一个交互式问题。

我想和你玩一个游戏……

我们向你隐藏了一个包含 $n$ 个顶点（$3 \le n \le 10^{18}$）的环图（cyclic graph）。环图是一个包含 $n$ 个顶点的无向图，这些顶点恰好构成一个单一的环。每个顶点都属于该环，即该环的长度（边的数量）恰好为 $n$。环中顶点的顺序是任意的。

你可以按如下方式发起查询：

• "? a b"，其中 $1 \le a, b \le 10^{18}$ 且 $a \neq b$。对于该查询，交互器将在单独一行输出从顶点 $a$ 到顶点 $b$ 的两条路径中随机一条的长度；若 $\max(a, b) > n$，则输出 -1。交互器以相等概率在两条路径中随机选择其一。路径长度定义为该路径所含边的数量。

如果你在不超过 $50$ 次查询内正确猜出隐藏图的顶点数（即数字 $n$），则获胜。

注意：交互器的实现保证，对任意有序对 $(a, b)$，无论查询多少次 "? a b"，其返回值始终相同。但请注意，查询 "? b a" 可能会得到不同的响应。

图中顶点的位置是随机分配的，且在交互开始前已固定。

本题禁止 hack。评测系统共包含 $50$ 个测试用例。

交互流程

你最多可发起 $50$ 次查询。每次查询需在单独一行输出：

• "? a b"，其中 $1 \le a, b \le 10^{18}$ 且 $a \neq b$。交互器将回应：从顶点 $a$ 到顶点 $b$ 的某条简单路径（注意：不是从 $b$ 到 $a$ 的路径）的长度（即边数），或当 $\max(a, b) > n$ 时输出 -1。交互器以相等概率在两条路径中随机选择其一。

若你的程序某次查询后收到结果 0，这表示你的解答已被判定为“答案错误”（例如：查询次数超过 $50$ 次，或发起了非法查询）。此时你的程序必须立即终止。否则，在此情形下你可能收到随机的其他判据，如“运行错误”、“超时”等，而非明确的“答案错误”。

答案输出格式与查询类似，也需在单独一行输出。答案输出不计入查询次数限制。请使用以下格式输出答案：

• "! n"：即你推测的隐藏图的大小（满足 $3 \le n \le 10^{18}$）。

此后，你的程序必须立即终止。

在输出下一次查询后，请务必调用流刷新函数，以确保你的输出不会滞留在缓冲区中。例如，在 C++ 中应调用 flush(stdout)，Java 中调用 System.out.flush()，Pascal 中调用 flush(output)，Python 中调用 stdout.flush()。

注意：交互器的实现保证，对任意有序对 $(a, b)$，无论查询多少次 "? a b"，其返回值始终相同。但请注意，查询 "? b a" 可能会得到不同的响应。

图中顶点的位置是随机分配的，且在交互开始前已固定。

本题禁止 hack。评测系统共包含 $50$ 个测试用例。

In the first example, the graph could look like this

The lengths of the simple paths between all pairs of vertices in this case are $1$ or $2$.

• The first query finds out that one of the simple paths from vertex $1$ to vertex $2$ has a length of $1$.
• With the second query, we find out that one of the simple paths from vertex $1$ to vertex $3$ has length $2$.
• In the third query, we find out that vertex $4$ is not in the graph. Consequently, the size of the graph is $3$.

在第一个例子中，图可能如下所示：

此时，所有顶点对之间的简单路径长度均为 $1$ 或 $2$。

• 第一个查询得知：顶点 $1$ 到顶点 $2$ 的某条简单路径长度为 $1$。
• 第二个查询得知：顶点 $1$ 到顶点 $3$ 的某条简单路径长度为 $2$。
• 第三个查询得知：顶点 $4$ 不在图中。因此，该图的大小为 $3$。