Background

Due to some bugs, submitting with C++14 (GCC9) will cause a compilation error. Please use C++14 and other languages to submit.

This problem is translated from JOISC 2024 Day4 T2 「島巡り / Island Hopping」. Translation source: LOJ.

Do not include island.h. You should add the following declarations at the top of your file:

int query(int, int);
void answer(int, int);

The interactive files can be downloaded from the JOI official website.

Problem Description

This is an interactive problem. The interactive library for this problem is non-adaptive.

The JOI country has $N$ islands, numbered from $1$ to $N$. There are $N-1$ routes, numbered from $1$ to $N-1$. Route $j\ (1\le j\le N-1)$ connects islands $A_j$ and $B_j$ bidirectionally. Starting from any island, you can reach any other island by traveling through some routes.

Aoi is going to travel in the JOI country. However, she does not know the routes in the JOI country. She plans to ask Bitaro, who lives in the JOI country, questions in the following way:

1. Aoi tells Bitaro two integers $v$ and $k$, where $1\le v\le N,1\le k\le N-1$.
2. Bitaro tells her the index of the $k$-th closest island to $v$ among the other $N-1$ islands (excluding $v$). More precisely, he tells an integer $i$ such that $\text{dist}(v,i)\times N+i\ (1\le i\le N,i\neq v)$ is the $k$-th smallest, where $\text{dist}(v,i)$ is the minimum number of routes used to travel from island $v$ to island $i$.

Aoi wants to find out all routes in the JOI country by asking questions. Since she does not want to spend too much time, she can ask Bitaro at most $L$ questions.

Given the number of islands and the limit on the number of questions, write a program to simulate Aoi’s questioning strategy and determine all routes.

Implementation Details

You need to include the library island.h at the beginning of your program.

You need to implement the following function.

• void solve(int N, int L)

  This function is called exactly once for each test case.

  • The parameter N is the number of islands $N$.
  • The parameter L is the question limit $L$.

In your program, you can call the following functions.

• int query(int v, int k)

  Aoi uses this function to ask Bitaro a question.

  • The parameter v must be between $1$ and $N$. Otherwise, your program will be judged Wrong Answer [1].
  • The parameter k must be between $1$ and $N-1$. Otherwise, your program will be judged Wrong Answer [2].
  • The return value is the index of the $k$-th closest island to $v$ among the other $N-1$ islands excluding $v$. See the statement for the precise definition.
  • You must not call query more than $L$ times. Otherwise, your program will be judged Wrong Answer [3].

• void answer(int x, int y)

  Use this function to report one route in the JOI country.

  • The parameters x and y are two islands connected by a route.
  • The parameters x and y must be between $1$ and $N$. Otherwise, your program will be judged Wrong Answer [4].
  • There must exist a route connecting islands x and y. In other words, there must exist an integer $j\ (1\le j\le N-1)$ such that $x=A_j,y=B_j$ or $x=B_j,y=A_j$. Otherwise, your program will be judged Wrong Answer [5].
  • Your program must not report the same route two or more times. Otherwise, your program will be judged Wrong Answer [6].
  • The function answer must be called exactly $N-1$ times. If, after solve finishes, the number of calls to this function is not $N-1$, your program will be judged Wrong Answer [7].

Notes

• You may implement other functions for internal use, or use global variables.
• Your program must not use standard input or standard output. Your program must not interact with other files in any way. However, your program may output debug information to standard error.
• The interactor used in the judging is not adaptive. This means the answer for each test case is fixed in advance.

Compilation and Execution

You can download the sample interactor in the attachments to test your program. The attached files also contain a sample program.

The sample interactor is the file grader.cpp. To test your program, put grader.cpp, island.cpp, and island.h in the same directory, and compile with the following command. You may also run compile.sh to compile your program.

g++ -std=gnu++20 -O2 -o grader grader.cpp island.cpp

If compilation succeeds, an executable file grader will be generated.

Note that the interactor used in the judging is different from the sample interactor. The sample interactor runs as a single process: it reads data from standard input and outputs results to standard output.

Input Format

The input format of the sample grader is as follows.

The first line contains two integers $N,L$.

The next $N-1$ lines each contain two integers $A_j,B_j$.

Output Format

The sample interactor will output the following information to standard output.

• If your program is judged correct, it will report the number of calls to query, for example: Accepted: 2024.
• If your program gets a certain Wrong Answer, the sample interactor will output its category, for example: Wrong Answer [4].

If your program satisfies multiple Wrong Answer categories, the sample interactor will report only one of them.

4 16
1 2
2 4
4 3

5 25
5 2
3 1
1 4
1 5

Hint

Sample Interaction

Sample Interaction $1$

The sample call process is shown in the table below.

The minimum numbers of routes needed to travel from island $2$ to islands $1,3,4$ are $1,2,1$, respectively. For example, to travel from island $2$ to island $3$, we can use route $2$ and then route $3$.

Sorting the islands by increasing $\text{dist}(2,i)\times N+i\ (i\neq 2)$ gives islands $1,4,3$. Therefore, the return value of query(2, 1) is $1$, and the return value of query(2, 2) is $4$.

Sample $1$ satisfies the constraints of subtasks $2,6$.

Sample Interaction $2$

The sample call process is shown in the table below.

The minimum numbers of routes needed to travel from island $1$ to islands $2,3,4,5$ are $2,1,1,1$, respectively. For example, to travel from island $1$ to island $2$, we can use route $4$ and then route $1$.

Sorting the islands by increasing $\text{dist}(1,i)\times N+i\ (i\neq 1)$ gives islands $3,4,5,2$. Therefore, the return value of query(1, 3) is $5$, and the return value of query(1, 4) is $2$.

Sample $2$ satisfies the constraints of subtasks $4,6$.

Constraints

• $3\le N\le 300$
• $1\le A_j,B_j\le N\ (1\le j\le N-1)$
• $A_j\neq B_j\ (1\le j\le N-1)$
• You can travel through routes from any island to any other island.

Subtasks

Translated by ChatGPT 5