题目描述

这是一道交互题。

Bissy 即将参加由志愿者组织的定向游戏 Final destination，EJOI 的各支代表队会在其中竞相访问城市里的不同地点。相比获胜，Bissy 对游戏的设计方式更感兴趣。

地图上有 $N$ 个地点和 $N$ 支队伍。每支队伍都要访问所有地点，并且起始地点各不相同：队伍 $i$ 从地点 $i$ 出发。每支队伍都有自己的路线。

这些路线基于一个由快速公共交通线路组成的隐藏结构。评测方选择了 $N-1$ 条线路，每条线路连接一对地点，并保证任意地点都能通过这些线路到达其他任意地点。这样的结构是一棵树。随后，对于每个起始地点 $i$，评测方生成了一次任意的 DFS 遍历，并将其作为队伍 $i$ 的路线。

Bissy 想找出隐藏的公共交通树。她可以询问：

队伍 $i$ 的第 $j$ 个目的地是什么？

请编写 find_tree 找出隐藏树。

树的一次 DFS 遍历是深度优先搜索中各顶点第一次被访问的顺序。搜索从给定顶点 $v$ 开始，递归前往某个尚未访问的相邻顶点；当不存在这样的顶点时，退回此前访问的顶点并继续。

:::align{center} :::

图中 $v=4$，边上的箭头表示深度优先搜索的步骤，生成的遍历为 $[4,1,2,0,3,6,7,5]$。访问相邻顶点的顺序会影响结果；另一次可能的遍历为 $[4,3,5,7,6,1,0,2]$。

树和全部 $N$ 次 DFS 遍历在程序开始前已经固定，不会根据你的询问发生改变。不同遍历使用的相邻顶点顺序可以不同。

实现细节

你需要实现：

std::vector<std::pair<int, int>> find_tree(int N)

• $N$：地点数；
• 返回值：由 $N-1$ 条树边组成的列表，边的顺序以及每条边两个端点的顺序均不限。

在每个测试中，该函数最多调用 $T$ 次。

你可以调用以下函数与评测器交互：

int guess(int i, int j)

它返回从地点 $i$ 出发的 DFS 遍历中第 $j$ 个地点。特别地，guess(i, 0) 会返回 $i$。在子任务 $0$ 至 $6$ 中，该函数会在 $O(1)$ 时间内返回；在子任务 $7$ 中，会在 $O(\log N)$ 时间内返回。必须满足 $0\le i,j\le N-1$，否则程序会得到 Output isn't correct: Invalid call。

输入格式

题目提供了两个样例评测器。

本地测试时，可将 Lgrader.cpp 与你的程序一起编译。程序先读入测试用例数 $T$。对于每个测试用例，先读入 $N$，再读入 $N-1$ 行树边，最后读入 $N$ 行、每行 $N$ 个整数，表示各次 DFS 遍历。第 $i$ 次遍历必须从顶点 $i$ 开始。将常量 AUTO_GENERATE 设为 true，可让评测器自动生成遍历。若结果错误，评测器会报告错误；否则会输出每个测试用例的询问次数及全局最大值。该评测器不支持足够大的 $N$，具体而言不支持子任务 $7$ 的限制。

系统用户测试可使用 stub.cpp 与你的程序一起编译。输入格式相同，但不提供自动生成遍历的功能。

提示

样例

假设隐藏的公共交通树如下：

假设从地点 $0$ 出发的遍历为 $[0,1,2,4,3,5]$。一次可能的交互如下：

这些询问提供的信息不足以唯一确定树，但这确实是子任务 $0$ 中该测试的答案。

限制

• $2\le N\le 2^{16}+1$
• 令 $N_{\max}$ 为同一测试内所有调用中 $N$ 的最大值：
  • 若 $N_{\max}\le 9$，则 $1\le T\le 100$；
  • 若 $N_{\max}\le 2^{10}+1$，则 $1\le T\le 10$；
  • 若 $N_{\max}\le 2^{16}+1$，则 $1\le T\le 3$。
• 系统评测器最多可使用 280 MiB 内存，这部分内存计入你的程序内存限制。

子任务

评分

对于子任务 $0$ 至 $5$，只要在时间限制内成功找出树即可获得满分。对于子任务 $6$ 和 $7$，令 $Q_{\max}$ 为某个测试中单个子测试使用的最大询问次数。该测试的得分比例 $S$ 为：

• 若 $Q_{\max}\le L_1$，则 $S=1.0$；
• 若 $L_1<Q_{\max}\le L_2$，则 $S=0.4+0.6\cdot\dfrac{L_2-Q_{\max}}{L_2-L_1}$；
• 若 $L_2<Q_{\max}\le 3L_2$，则 $S=0.2+0.2\cdot\dfrac{3L_2-Q_{\max}}{2L_2}$；
• 若 $3L_2<Q_{\max}$，则 $S=0.2$。

对于子任务 $6$，$L_1=3(2^{10}+1)=3075$，$L_2=9(2^{10}+1)=9225$。对于子任务 $7$，$L_1=3(2^{16}+1)=196611$，$L_2=15(2^{16}+1)=983055$。整个子任务的得分比例是所有测试中 $S$ 的最小值。