Problem Description

This is an interactive problem.

Bissy is about to enter the volunteer-organized orienteering game Final destination, where EJOI delegations compete to visit locations across the city. She is more interested in how the game was designed than in winning it.

There are $N$ locations and $N$ teams. Every team must visit all locations, and the teams have distinct starting locations: team $i$ starts from location $i$. Each team receives its own route.

The routes are based on a hidden structure of fast public transport lines. The jury chose $N-1$ lines, each connecting two locations, so that every location is reachable from every other location. This structure is a tree. For every starting location $i$, the jury generated an arbitrary DFS walk and assigned it as team $i$'s route.

Bissy wants to discover the hidden tree. She may ask questions of the form:

What is the $j$-th destination of team $i$?

Write find_tree to find the hidden tree.

A DFS walk of a tree is the order in which its vertices are first visited by depth-first search. Starting at a vertex $v$, the procedure repeatedly moves recursively to an unvisited neighbor. When none remains, it returns to the previously visited vertex and continues.

:::align{center} :::

In the figure, $v=4$ and the arrows show the steps of a DFS. The generated walk is $[4,1,2,0,3,6,7,5]$. The order in which neighbors are visited matters; another possible walk is $[4,3,5,7,6,1,0,2]$.

The tree and all $N$ DFS walks are fixed before your program starts and do not change in response to your questions. Different DFS walks may use different neighbor orders.

Implementation details

Implement:

std::vector<std::pair<int, int>> find_tree(int N)

• $N$: the number of locations;
• return value: a list of $N-1$ tree edges. The order of the edges and the order of their endpoints do not matter.

For each test, this function may be called up to $T$ times.

To interact with the jury, call:

int guess(int i, int j)

It returns the $j$-th location in the DFS walk starting at $i$. In particular, guess(i, 0) returns $i$. The function responds in constant time $O(1)$ for subtasks $0$ through $6$, and in logarithmic time $O(\log N)$ for subtask $7$. You must have $0\le i,j\le N-1$; otherwise, your solution receives Output isn't correct: Invalid call.

Input Format

Two sample graders are provided.

For local testing, Lgrader.cpp can be compiled with your program. It reads the number $T$ of test cases. For every case, it reads $N$, then $N-1$ lines of edges, then $N$ lines of $N$ integers describing the DFS walks. Walk $i$ must start at vertex $i$. Set AUTO_GENERATE to true to let the grader generate the walks. The grader reports an error if the result is incorrect; otherwise, it reports the number of queries for every test case and the overall maximum. This grader does not support sufficiently large $N$, namely the constraints of subtask $7$.

For system user tests, stub.cpp can be used with your program. Its input format is the same, but it has no built-in walk generation.

Hint

Example

Assume the hidden public transport tree is:

:::align{center} :::

For starting location $0$, suppose the walk is $[0,1,2,4,3,5]$. One possible interaction is:

The queries do not uniquely determine the tree, but this is the answer to the test in subtask $0$.

Constraints

• $2\le N\le 2^{16}+1$
• Let $N_{\max}$ be the maximum $N$ among calls in one test:
  • if $N_{\max}\le 9$, then $1\le T\le 100$;
  • if $N_{\max}\le 2^{10}+1$, then $1\le T\le 10$;
  • if $N_{\max}\le 2^{16}+1$, then $1\le T\le 3$.
• The system grader may use up to 280 MiB, which counts toward your solution's memory.

Subtasks

Scoring

For subtasks $0$ through $5$, you receive full points if you find the tree within the time limit. For subtasks $6$ and $7$, let $Q_{\max}$ be the maximum number of queries used on one subtest. The score fraction $S$ for a test is:

• if $Q_{\max}\le L_1$, then $S=1.0$;
• if $L_1<Q_{\max}\le L_2$, then $S=0.4+0.6\cdot\dfrac{L_2-Q_{\max}}{L_2-L_1}$;
• if $L_2<Q_{\max}\le 3L_2$, then $S=0.2+0.2\cdot\dfrac{3L_2-Q_{\max}}{2L_2}$;
• if $3L_2<Q_{\max}$, then $S=0.2$.

For subtask $6$, $L_1=3(2^{10}+1)=3075$ and $L_2=9(2^{10}+1)=9225$. For subtask $7$, $L_1=3(2^{16}+1)=196611$ and $L_2=15(2^{16}+1)=983055$. The score fraction for the whole subtask is the minimum $S$ among all tests.

:::align{center} :::