{"raw_statement":[{"iden":"background","content":"**由于部分 BUG，使用 C++14 (GCC9) 提交会产生编译错误，请使用 C++14 等语言进行提交。**\n\n**题目译自 [JOISC 2024](https://www2.ioi-jp.org/camp/2024/2024-sp-tasks/index.html) Day4 T2 「[島巡り](https://www2.ioi-jp.org/camp/2024/2024-sp-tasks/contest4/island.pdf) / [Island Hopping](https://www2.ioi-jp.org/camp/2024/2024-sp-tasks/contest4/island-en.pdf)」**。翻译来源 LOJ。\n\n**不要引入 `island.h`**。你应该在文件头添加以下声明：\n\n```\nint query(int, int);\nvoid answer(int, int);\n```\n\n交互文件可在 [JOI 官网](https://www2.ioi-jp.org/camp/2024/2024-sp-tasks/index.html)下载。"},{"iden":"statement","content":"**这是一道交互题。本题交互库是非自适应的。**\n\nJOI 国有 $N$ 座岛屿，编号为 $1$ 到 $N$。有 $N-1$ 条航线，编号为 $1$ 到 $N-1$。航线 $j\\ (1\\le j\\le N-1)$ 双向连接岛屿 $A_j$ 和 $B_j$。可以从一座岛屿出发，通过一些航线到达任意另一个岛屿。\n\n葵准备在 JOI 国旅行。然而她不知道 JOI 国的航线。她准备向 JOI 国居住的 Bitaro 按下面的方式提一些问题：\n\n1. 葵告诉 Bitaro 两个整数 $v$ 和 $k$，其中 $1\\le v\\le N,1\\le k\\le N-1$。\n2. 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$ 所经过的最小航线数。\n\n葵想通过提问知道所有 JOI 国的航线。因为葵不想花费太多时间，所以她最多只能向 Bitaro 问 $L$ 个问题。\n\n给定 JOI 国的岛屿数和提问限制数，写一个程序模拟葵的提问策略，以找出所有的航线。\n\n### 实现细节\n\n你需要在程序开头引入库 `island.h`。\n\n你需要实现如下函数。\n\n- `void solve(int N, int L)`\n\n  此函数在每个测试点中只被调用一次\n\n  - 参数 `N` 是岛屿数 $N$\n  - 参数 `L` 是提问次数限制 $L$。\n\n在程序中，你可以调用如下函数。\n\n- `int query(int v, int k)`\n\n  葵使用此函数向 Bitaro 提问\n\n  - 参数 `v` 必须在 $1$ 到 $N$ 之间。如果不是，你的程序会被判为 **Wrong Answer [1]**。\n  - 参数 `k` 必须在 $1$ 到 $N-1$​ 之间。如果不是，你的程序会被判为 **Wrong Answer [2]**。\n  - 返回值表示除 $v$ 之外的其他 $N-1$ 个岛屿中，距离 $v$ 第 $k$ 近的岛屿编号。参考题目描述获得更详细的定义。\n  - 你不能调用 `query` 函数超过 $L$ 次，否则你的程序会被判为 **Wrong Answer [3]**。\n\n- `void answer(int x, int y)`\n\n  使用此函数回答 JOI 国的一条航线\n\n  - 参数 `x` 和 `y` 表示被一条航线连接的两座岛屿。\n  - 参数 `x` 和 `y` 必须在 $1$ 到 $N$ 之间。如果不是，你的程序会被判为 **Wrong Answer [4]**。\n  - 必须存在一条连接岛屿 `x` 和 `y` 的航线。换句话说，必须存在一个整数 $j\\ (1\\le j\\le N-1)$ 满足 $x=A_j,y=B_j$ 或 $x=B_j,y=A_j$。否则，你的程序会被判为 **Wrong Answer [5]**。\n  - 你的程序不能回答相同的航线两次或以上。否则，你的程序会被判为 **Wrong Answer [6]**。\n  - 函数 `answer` 必须被调用恰好 $N-1$ 次。如果 `solve` 函数运行结束后此函数调用次数不是 $N-1$，你的程序会被判为 **Wrong Answer [7]**。\n  \n### 注意事项\n\n- 你的程序可以实现其它函数供内部使用，或者使用全局变量。\n- 你的程序禁止使用标准输入输出。你的程序禁止与其他文件通过任何方式交互。然而，你的程序可以使用标准错误输出输出调试信息。\n- 测评中使用的交互器**不是**自适应性的。这意味着每组测试点的答案是提前确定好的。\n\n### 编译运行\n\n你可以在附件中下载样例交互器来测试你的程序。附加文件中还包含一个样例程序。\n\n样例交互器是文件 `grader.cpp`。为了测试你的程序，请将 `grader.cpp`，`island.cpp` 和 `island.h` 放在同一目录下，并且执行如下命令编译程序。此外你也可以运行 `compile.sh` 来编译你的程序。\n\n```bash\ng++ -std=gnu++20 -O2 -o grader grader.cpp island.cpp\n```\n\n当编译成功时，会生成可执行文件 `grader`。\n\n注意测评时使用的交互器与样例交互器不同。样例交互器会以单进程的形式执行，它会从标准输入中读入数据，输出结果到标准输出。"},{"iden":"input","content":"Sample Grader 输入格式如下：\n\n第一行两个整数 $N,L$。\n\n接下来 $N-1$ 行，每行两个整数 $A_j,B_j$。"},{"iden":"output","content":"样例交互器将向标准输出中输出如下信息：\n\n\n- 如果你的程序被判为正确，它会报告调用 `query` 的次数，如：`Accepted: 2024`。\n- 如果你的程序被判为某种 Wrong Answer，样例交互程序会输出它的类别，如：`Wrong Answer [4]`。\n\n如果你的程序满足多种 Wrong Answer 的类别，样例交互器只会报告其中一个。"},{"iden":"note","content":"### 样例交互\n\n#### 样例交互 $1$\n\n样例调用过程如下表所示。\n\n|      调用      |      调用      | 返回值 |\n| :------------: | :------------: | :----: |\n| `solve(4, 16)` |               |        |\n|                | `query(2, 1)`  |  $1$   |\n|                | `query(3, 1)`  |  $4$   |\n|                | `answer(2, 4)` |        |\n|                | `query(2, 2)`  |  $4$   |\n|                | `answer(2, 1)` |        |\n|                | `query(3, 2)`  |  $2$   |\n|                | `query(2, 1)`  |  $1$   |\n|                | `answer(3, 4)` |        |\n\n从岛屿 $2$ 到岛屿 $1,3,4$ 的最小经过航线数分别为 $1,2,1$。例如，从岛屿 $2$ 到岛屿 $3$，我们可以使用航线 $2$ 后使用航线 $3$。\n\n将岛屿按 $\\text{dist}(2,i)\\times N+i\\ (i\\neq 2)$ 递增的顺序排序，结果是岛屿 $1,4,3$。因此，`query(2, 1)` 的返回值为 $1$，`query(2, 2)` 的返回值为 $4$。\n\n样例 $1$ 满足子任务 $2,6$ 的限制。\n\n#### 样例交互 $2$\n\n\n样例调用过程如下表所示。\n\n|      调用      |      调用      | 返回值 |\n| :------------: | :------------: | :----: |\n| `solve(5, 25)` |            |        |\n|                | `query(1, 3)`  |  $5$   |\n|                | `query(1, 4)`  |  $2$   |\n|                | `answer(3, 1)` |        |\n|                | `query(2, 4)`  |  $4$   |\n|                | `query(3, 1)`  |  $1$   |\n|                | `query(3, 2)`  |  $4$   |\n|                | `answer(1, 5)` |        |\n|                | `answer(4, 1)` |      |\n|                | `answer(2, 5)`  |        |\n\n从岛屿 $1$ 到岛屿 $2,3,4,5$ 的最小经过航线数分别为 $2,1,1,1$。例如，从岛屿 $1$ 到岛屿 $2$，我们可以使用航线 $4$ 后使用航线 $1$。\n\n将岛屿按 $\\text{dist}(1,i)\\times N+i\\ (i\\neq 1)$ 递增的顺序排序，结果是岛屿 $3,4,5,2$。因此，`query(1, 3)` 的返回值为 $5$，`query(1, 4)` 的返回值为 $2$。\n\n样例 $2$ 满足子任务 $4,6$ 的限制。\n\n### 数据范围\n\n- $3\\le N\\le 300$\n- $1\\le A_j,B_j\\le N\\ (1\\le j\\le N-1)$\n- $A_j\\neq B_j\\ (1\\le j\\le N-1)$\n- 可以通过航线，从一个岛屿到达任意其他岛屿\n\n### 子任务\n\n| 子任务 |                           附加限制                           | 分值 |\n| :----: | :----------------------------------------------------------: | :--: |\n|  $1$   |                          $N=3,L=9$                           | $2$  |\n|  $2$   |             $L=N^2$，每座岛屿最多有两条航线连接              | $4$  |\n|  $3$   |              $L=2N$，每座岛屿最多有两条航线连接              | $7$  |\n|  $4$   | $L=N^2$，岛屿 $1$ 有三条航线连接，其他每座岛屿最多有两条航线连接 | $9$  |\n|  $5$   | $L=3N$，岛屿 $1$ 有三条航线连接，其他每座岛屿最多有两条航线连接 | $13$ |\n|  $6$   |                           $L=N^2$                            | $15$ |\n|  $7$   |                            $L=3N$                            | $22$ |\n|  $8$   |                            $L=2N$                            | $28$ |"}],"translated_statement":null,"sample_group":[["4 16\n1 2\n2 4\n4 3",""],["5 25\n5 2\n3 1\n1 4\n1 5",""]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}