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.
Your task is to help Kipa determine the length of the directed cycle for each hedgehog graph.
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.
Once you have determined the length of the cycle $$$s$$$, output ! s. After that, read a single integer which is either:
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.
1 3 7 10 1
? 1 2 ? 2 5 ? 10 11 ! 11
Provider CodeForces Gym
AC Rate 0%
Date 10/31/2021 14:45:12