JOI 王国共有 $N$ 座岛屿，编号为 $1$ 到 $N$。JOI 王国共有 $N-1$ 条海上航线，编号为 $1$ 到 $N-1$。第 $j$ 条海上航线（$1 \le j \le N-1$）双向连接岛屿 $A_j$ 和岛屿 $B_j$。通过这些海上航线，可以从任意岛屿到达其他任意岛屿。

Aoi 正在计划一次 JOI 王国的旅行。然而，她并不了解 JOI 王国的海上航线。她打算通过以下方式向 JOI 王国的公民 Bitaro 提问：

1. Aoi 告诉 Bitaro 一个整数 $v$（$1 \le v \le N$）和一个整数 $k$（$1 \le k \le N-1$）。
2. Bitaro 告诉 Aoi 在除岛屿 $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$ 所需的最少海上航线数。

Aoi 希望通过向 Bitaro 提问来获知所有的海上航线。由于 Aoi 不想花费太多时间，她最多可以向 Bitaro 提出 $L$ 个问题。

请编写一个程序，在给定岛屿数量和提问次数限制的情况下，实现 Aoi 寻找所有海上航线的策略。

实现细节

你需要提交一个文件。 文件名为 island.cpp。它应该实现以下函数。程序应使用预处理指令 #include 包含 island.h。

• void solve(int N, int L) 该函数对每个测试用例仅调用一次。
  • 参数 $N$ 是岛屿的数量。
  • 参数 $L$ 是提问次数的限制。

在 island.cpp 中，你可以调用以下函数：

• int query(int v, int k) 使用此函数，Aoi 向 Bitaro 提问。

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

• void answer(int x, int y) 你的程序通过调用此函数来回答一条海上航线。

  • 参数 $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 函数执行结束时 answer 函数的调用次数不是 $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。 请注意，实际的评测程序与样例评测程序不同。样例评测程序将作为一个单独的进程执行，它会从标准输入读取数据并将结果写入标准输出。

数据范围

所有输入数据满足以下条件：

• $3 \le N \le 300$。
• $1 \le A_j \le N$（$1 \le j \le N-1$）。
• $1 \le B_j \le N$（$1 \le j \le N-1$）。
• $A_j \neq B_j$（$1 \le j \le N-1$）。
• 可以通过海上航线从任意岛屿到达其他任意岛屿。
• 给定值均为整数。

子任务

1. (2 分) $N = 3, L = 9$。
2. (4 分) $L = N^2$。每座岛屿最多有 2 条连接的海上航线。
3. (7 分) $L = 2N$。每座岛屿最多有 2 条连接的海上航线。
4. (9 分) $L = N^2$。岛屿 1 有 3 条连接的海上航线，其余每座岛屿最多有 2 条连接的海上航线。
5. (13 分) $L = 3N$。岛屿 1 有 3 条连接的海上航线，其余每座岛屿最多有 2 条连接的海上航线。
6. (15 分) $L = N^2$。
7. (22 分) $L = 3N$。
8. (28 分) $L = 2N$。

样例

输入格式 1

4 16

输出格式 1

(由程序通过 answer 函数输出)

说明

在样例 1 中，从岛屿 2 到岛屿 1、3、4 的最少海上航线数分别为 1、2、1。例如，要从岛屿 2 到达岛屿 3，我们可以先走航线 2，再走航线 3。 将岛屿 $i$（$i \neq 2$）按 $\text{dist}(2, i) \times N + i$ 的升序排列，结果依次为岛屿 1、岛屿 4、岛屿 3。因此，query(2, 1) 的返回值为 1，query(2, 2) 的返回值为 4。

输入格式 2

5 25

输出格式 2

(由程序通过 answer 函数输出)

说明

在样例 2 中，从岛屿 1 到岛屿 2、3、4、5 的最少海上航线数分别为 2、1、1、1。例如，要从岛屿 1 到达岛屿 2，我们可以先走航线 4，再走航线 1。 将岛屿 $i$（$i \neq 1$）按 $\text{dist}(1, i) \times N + i$ 的升序排列，结果依次为岛屿 3、岛屿 4、岛屿 5、岛屿 2。因此，query(1, 3) 的返回值为 5，query(1, 4) 的返回值为 2。