Hedgehog Graph

5000ms

1048576K

Description:

A hedgehog graph is a directed graph where each vertex has exactly one outgoing edge and contains exactly one directed cycle of length at least 3 (the graph does not contain a loop or cycle of length 2.) For every edge $$$e = u \rightarrow v$$$ in the hedgehog graph, $$$v$$$ belongs to the aforementioned single directed cycle.

For a vertex $$$v$$$, if there exists an edge $$$v \rightarrow w$$$, we denote the vertex $$$w = next(v)$$$ as the next vertex. This vertex exists and is unique.

Kipa has $$$n$$$ hedgehog graphs with $$$10^6$$$ vertices. Each vertex is numbered from $$$1$$$ to $$$10^6$$$. Kipa is not given the graph directly. Instead, Kipa can ask the following query at most $$$900$$$ times.

? v x: Given a vertex $$$v$$$ and a positive integer $$$x$$$, the jury starts at $$$v$$$, moves to the next vertex $$$x$$$ times, and returns the index of the resulting vertex. ($$$1 \le v \le 10^6, 1 \le x \le 5 \times 10^{18}$$$)

Your task is to help Kipa determine the length of the directed cycle for each hedgehog graph.

Output:

First, your program must read from the standard input one line with the positive integer $$$n$$$, the number of graphs to process. $$$n$$$ will be at most $$$10$$$.

For each graph, the program can ask the following query at most $$$900$$$ times.

? v x: Given a vertex $$$v$$$ and a positive integer $$$x$$$, the jury starts at $$$v$$$, moves to the next vertex $$$x$$$ times, and returns the index of the resulting vertex. ($$$1 \le v \le 10^6, 1 \le x \le 5 \times 10^{18}$$$)

Once you have determined the length of the cycle $$$s$$$, output ! s. After that, read a single integer which is either:

$$$1$$$, if the answer is correct. You should immediately start processing the next graph, or finish your program with the exit code 0 if all $$$n$$$ graphs are processed.
$$$-1$$$, if the answer is incorrect. In this case, you should finish your program with exit code 0, in which case you will receive a Wrong Answer verdict. Failure to handle this properly may result in unexpected behavior.

You must flush your output after every interaction.

The interactor is adaptive. In other words, the interactor does not necessarily start with a fixed graph at the beginning of the interaction. The interactor only guarantees that there exists at least one hedgehog graph that satisfies all the provided responses of the interactor and the input specification.

Sample Input:

Sample Output:

Info

Provider CodeForces Gym

Origin XXII Open Cup. Grand Prix of Korea

Code GYM103371F