题目背景

题目译自 JOISC 2024 Day4 T2 「島巡り / Island Hopping」。翻译来源 LOJ。

不要引入 island.h。你应该在文件头添加以下声明：

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

交互文件可在 JOI 官网下载。

题目描述

这是一道交互题。本题交互库是非自适应的。

JOI 国有 $N$ 座岛屿，编号为 $1$ 到 $N$。有 $N-1$ 条航线，编号为 $1$ 到 $N-1$。航线 $j\ (1\le j\le N-1)$ 双向连接岛屿 $A_j$ 和 $B_j$。可以从一座岛屿出发，通过一些航线到达任意另一个岛屿。

葵准备在 JOI 国旅行。然而她不知道 JOI 国的航线。她准备向 JOI 国居住的 Bitaro 按下面的方式提一些问题：

1. 葵告诉 Bitaro 两个整数 $v$ 和 $k$，其中 $1\le v\le N,1\le k\le N-1$。
2. Bitaro 会告诉她除了 $v$ 之外的其他 $N-1$ 座岛屿中，距离 $v$ 第 $k$ 近的岛屿编号。更确切地说，他会告诉她一个整数 $i$，满足 $\text{dist}(v,i)\times N+i\ (1\le i\le N,i\neq v)$ 是第 $k$ 小的，其中 $\text{dist}(v,i)$ 是从岛屿 $v$ 到 $i$ 所经过的最小航线数。

葵想通过提问知道所有 JOI 国的航线。因为葵不想花费太多时间，所以她最多只能向 Bitaro 问 $L$ 个问题。

给定 JOI 国的岛屿数和提问限制数，写一个程序模拟葵的提问策略，以找出所有的航线。

实现细节

你需要在程序开头引入库 island.h。

你需要实现如下函数。

• void solve(int N, int L)

  此函数在每个测试点中只被调用一次

  • 参数 N 是岛屿数 $N$
  • 参数 L 是提问次数限制 $L$。

在程序中，你可以调用如下函数。

• int query(int v, int k)

  葵使用此函数向 Bitaro 提问

  • 参数 v 必须在 $1$ 到 $N$ 之间。如果不是，你的程序会被判为 Wrong Answer [1]。
  • 参数 k 必须在 $1$ 到 $N-1$​ 之间。如果不是，你的程序会被判为 Wrong Answer [2]。
  • 返回值表示除 $v$ 之外的其他 $N-1$ 个岛屿中，距离 $v$ 第 $k$ 近的岛屿编号。参考题目描述获得更详细的定义。
  • 你不能调用 query 函数超过 $L$ 次，否则你的程序会被判为 Wrong Answer [3]。

• void answer(int x, int y)

  使用此函数回答 JOI 国的一条航线

  • 参数 x 和 y 表示被一条航线连接的两座岛屿。
  • 参数 x 和 y 必须在 $1$ 到 $N$ 之间。如果不是，你的程序会被判为 Wrong Answer [4]。
  • 必须存在一条连接岛屿 x 和 y 的航线。换句话说，必须存在一个整数 $j\ (1\le j\le N-1)$ 满足 $x=A_j,y=B_j$ 或 $x=B_j,y=A_j$。否则，你的程序会被判为 Wrong Answer [5]。
  • 你的程序不能回答相同的航线两次或以上。否则，你的程序会被判为 Wrong Answer [6]。
  • 函数 answer 必须被调用恰好 $N-1$ 次。如果 solve 函数运行结束后此函数调用次数不是 $N-1$，你的程序会被判为 Wrong Answer [7]。

注意事项

• 你的程序可以实现其它函数供内部使用，或者使用全局变量。
• 你的程序禁止使用标准输入输出。你的程序禁止与其他文件通过任何方式交互。然而，你的程序可以使用标准错误输出输出调试信息。
• 测评中使用的交互器不是自适应性的。这意味着每组测试点的答案是提前确定好的。

编译运行

你可以在附件中下载样例交互器来测试你的程序。附加文件中还包含一个样例程序。

样例交互器是文件 grader.cpp。为了测试你的程序，请将 grader.cpp，island.cpp 和 island.h 放在同一目录下，并且执行如下命令编译程序。此外你也可以运行 compile.sh 来编译你的程序。

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

当编译成功时，会生成可执行文件 grader。

注意测评时使用的交互器与样例交互器不同。样例交互器会以单进程的形式执行，它会从标准输入中读入数据，输出结果到标准输出。

输入格式

Sample Grader 输入格式如下：

第一行两个整数 $N,L$。

接下来 $N-1$ 行，每行两个整数 $A_j,B_j$。

输出格式

样例交互器将向标准输出中输出如下信息：

• 如果你的程序被判为正确，它会报告调用 query 的次数，如：Accepted: 2024。
• 如果你的程序被判为某种 Wrong Answer，样例交互程序会输出它的类别，如：Wrong Answer [4]。

如果你的程序满足多种 Wrong Answer 的类别，样例交互器只会报告其中一个。

4 16
1 2
2 4
4 3

5 25
5 2
3 1
1 4
1 5

提示

样例交互

样例交互 $1$

样例调用过程如下表所示。

调用		返回值
solve(4, 16)
	query(2, 1)	$1$
	query(3, 1)	$4$
	answer(2, 4)
	query(2, 2)	$4$
	answer(2, 1)
	query(3, 2)	$2$
	query(2, 1)	$1$
	answer(3, 4)

从岛屿 $2$ 到岛屿 $1,3,4$ 的最小经过航线数分别为 $1,2,1$。例如，从岛屿 $2$ 到岛屿 $3$，我们可以使用航线 $2$ 后使用航线 $3$。

将岛屿按 $\text{dist}(2,i)\times N+i\ (i\neq 2)$ 递增的顺序排序，结果是岛屿 $1,4,3$。因此，query(2, 1) 的返回值为 $1$，query(2, 2) 的返回值为 $4$。

样例 $1$ 满足子任务 $2,6$ 的限制。

样例交互 $2$

样例调用过程如下表所示。

调用		返回值
solve(5, 25)
	query(1, 3)	$5$
	query(1, 4)	$2$
	answer(3, 1)
	query(2, 4)	$4$
	query(3, 1)	$1$
	query(3, 2)	$4$
	answer(1, 5)
	answer(4, 1)
	answer(2, 5)

从岛屿 $1$ 到岛屿 $2,3,4,5$ 的最小经过航线数分别为 $2,1,1,1$。例如，从岛屿 $1$ 到岛屿 $2$，我们可以使用航线 $4$ 后使用航线 $1$。

将岛屿按 $\text{dist}(1,i)\times N+i\ (i\neq 1)$ 递增的顺序排序，结果是岛屿 $3,4,5,2$。因此，query(1, 3) 的返回值为 $5$，query(1, 4) 的返回值为 $2$。

样例 $2$ 满足子任务 $4,6$ 的限制。

数据范围

• $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)$
• 可以通过航线，从一个岛屿到达任意其他岛屿

子任务

子任务	附加限制	分值
$1$	$N=3,L=9$	$2$
$2$	$L=N^2$，每座岛屿最多有两条航线连接	$4$
$3$	$L=2N$，每座岛屿最多有两条航线连接	$7$
$4$	$L=N^2$，岛屿 $1$ 有三条航线连接，其他每座岛屿最多有两条航线连接	$9$
$5$	$L=3N$，岛屿 $1$ 有三条航线连接，其他每座岛屿最多有两条航线连接	$13$
$6$	$L=N^2$	$15$
$7$	$L=3N$	$22$
$8$	$L=2N$	$28$