JOI Islands Interactive Exploration

This is an interactive problem. In the country of JOI, there are (N) islands numbered from (1) to (N), connected by (N-1) bidirectional flights. The flights are numbered from (1) to (N-1). For each flight (j) ((1 \le j \le N-1)), it connects island (A_j) and island (B_j). It is guaranteed that one can travel between any two islands via some sequence of flights.

Aoi is planning a trip in JOI but she does not know the flight routes. Therefore, she will ask Bitaro some queries in order to discover all the flights in JOI according to the following procedure:

1. Aoi provides two integers (v) and (k) with (1 \le v \le N) and (1 \le k \le N-1).
2. Bitaro replies with an island number (i) (with (1 \le i \le N,\ i \neq v)) such that the value (\mathrm{dist}(v,i) \times N + i) is the (k^\text{th}) smallest among all islands other than (v). Here, (\mathrm{dist}(v,i)) denotes the minimum number of flights required to travel from island (v) to island (i).

Aoi can ask at most (L) queries. Your task is to implement Aoi’s questioning strategy to eventually determine all the flight routes in JOI.

\textbf{Implementation details:}

You must include the header file island.h at the beginning of your program. You are required to implement the following function:

\begin{itemize} \item void solve(int N, int L)\ This function is called exactly once per test case. It receives the number of islands (N) and the query limit (L). \end{itemize}

In your program you can call the following functions:

\begin{itemize} \item int query(int v, int k)\ Aoi uses this function to ask Bitaro a query. The parameter (v) must satisfy (1 \le v \le N) and (k) must satisfy (1 \le k \le N-1). If these conditions are violated, your program will receive an error. The returned integer represents the island number which is the (k^\text{th}) closest to (v) among all islands except (v), where closeness is defined by the value (\mathrm{dist}(v,i) \times N + i).

\item void answer(int x, int y)\ Use this function to answer that there is a flight connecting islands (x) and (y). The parameters (x) and (y) must satisfy (1 \le x, y \le N) and there must exist an index (j) ((1 \le j \le N-1)) such that either (x=A_j,\ y=B_j) or (x=B_j,\ y=A_j). You must call this function exactly (N-1) times, once for each flight. Repeated answers or calling with an incorrect flight will cause your solution to be rejected. \end{itemize}

\textbf{Note:} \begin{itemize} \item The interactor in this problem is non-adaptive; that is, all answers are fixed in advance for each test case. \item Your program must not use standard input/output, nor interact with any files. It is permitted to print debug information to the standard error stream. \end{itemize}

\textbf{Compilation and Execution:}

A sample interactive grader is provided in the file grader.cpp along with island.cpp and island.h. To compile, for example, using g++ run:

\begin{verbatim} g++ -std=gnu++20 -O2 -o grader grader.cpp island.cpp \end{verbatim}

Once compiled, the executable grader can be used to test your solution. Note that the interactor used in the contest will be different from the sample one provided.

inputFormat

This is an interactive problem. The function solve is provided with two integers as parameters: N representing the number of islands and L representing the maximum number of queries allowed. There is no traditional input through standard input.

outputFormat

Your solution must call the function answer(x, y) exactly N-1 times to report all the flight routes in JOI. There is no direct output to standard output.

sample

5 10
# The hidden flight configuration is a star centered at island 1: flights (1,2), (1,3), (1,4), (1,5).

1 2
1 3
1 4
1 5

</p>