Description:
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) > 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$$$.
Input Format:
None
Output Format:
None
Note:
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$$$.