Interactive Graph (Hard Version)

Research used: the official Codeforces editorial for Round 1079 shows the accepted C2 code pattern; the official problem statement is the canonical spec; this CSDN explanation independently describes the same prefix-block and path-count reuse idea.

This is still an interactive solution. The hack input format is for the interactor/test data; the submitted program reconstructs the graph by asking ? k and finally printing ! m. Reading m directly would be solving the wrong damn problem.

For any vertex $v$, define $F(v)$ as the number of paths that start at $v$, including the length-$1$ path. If the outgoing edges of $v$ go to vertices $to$, then

$F(v)=1+\sum_{(v,to)\in E} F(to).$

The key observation is stronger than it first looks: for any already fixed valid prefix $P$ ending at $v$, all complete paths beginning with $P$ form one contiguous segment in lexicographic order, and that segment has size exactly $F(v)$. The segment is ordered as: first $P$ itself, then for each outgoing neighbor in increasing vertex-label order, the whole segment for that neighbor. So the global path list is basically DFS preorder on the trie of all paths, except identical suffix subproblems repeat whenever the same graph vertex is reached through another prefix.

If we queried every path one by one, two consecutive paths would reveal movement in this DFS preorder. Let prev be the previous path and cur be the current path, and let lcp be their longest common prefix length. If lcp > 0, then cur[lcp - 1] -> cur[lcp] is the edge that enters the next child block, so it is a real graph edge and should be recorded. This is the simple part.

The hard version needs at most $n+m$ queries, so walking every path is impossible; there may be exponentially many. The escape hatch is memoization of $F(v)$. Once the scan leaves a prefix containing some vertex $v$, the whole block for that occurrence of $v$ is over forever. At that moment, all outgoing edges of $v$ have already been discovered, and because the graph is a DAG, $F(v)$ can be computed recursively as $1+\sum F(to)$. Later, if another queried path reaches the same vertex $v$, we do not need to inspect all paths below it again. We can jump over exactly $F(v)$ paths.

Algorithm:

1. The first path is always $[1]$, so set prev = [1] and start with k = 2. Skipping ? 1 is important because the final empty query also costs one.
2. Ask for the $k$-th path. If the answer is empty, all paths are done.
3. Compute lcp(prev, cur).
4. If prev has a vertex immediately after the LCP, that vertex's block just ended, so compute its $F$ value from the discovered graph.
5. If lcp > 0, add edge cur[lcp - 1] -> cur[lcp].
6. If $F(cur[lcp])$ is already known, set k += F(cur[lcp]); otherwise set k++.
7. Replace prev by cur.

Why this finds every edge: consider any real edge $u \to v$. The first time the DFS-style path order enters the child block for $v$ after some prefix ending at $u$, the current path differs from the previous path exactly at the position of $v$, so the LCP rule records $u \to v$. If the algorithm later skips a block starting at $v$, then $F(v)$ was already known, meaning all edges reachable from $v$ were already discovered earlier. No edge is silently lost; skipped work is only repeated suffix work.

Why the query count fits: every non-empty query with lcp > 0 records one new edge, so there are at most $m$ such queries. Every non-empty query with lcp = 0 is a singleton path starting a new first vertex; since $[1]$ was known for free, there are at most $n-1$ of those. Then there is exactly one final empty query. Total: $m+(n-1)+1=n+m$. Cute budget design, not a coincidence.

Edge cases are clean. For $n=1$, ? 2 returns empty and the answer is zero edges. Isolated vertices only create singleton queries. Edges may go from a larger label to a smaller label; nothing assumes labels are topological order. The only structural assumption used is acyclicity, so the recursive path counts terminate.

Local work is tiny: each LCP comparison costs $O(n)$, and there are at most $n+m$ queries, so computation is $O(n(n+m))$ with $O(n+m)$ memory. The real complexity metric is the query count: at most $n+m$.