题目描述

题目译自 JOISC 2019 Day1 T2「ビーバーの会合 / Meetings」

有 $N$ 座住有海狸的岛屿，编号从 $0$ 至 $N - 1$。这些岛由 $N - 1$ 条双向桥梁连接，使得两两互相可达。保证每个岛屿至多连出 $\mathbf{18}$ 座桥。每个岛住有一只海狸。

有时，一些海狸会赶往同一个岛屿进行聚会。当三只海狸进行聚会的时候，它们会按照这一规则选择聚会的岛屿：

找到一个岛屿，使得三只海狸到达这个岛屿的距离之和是最小的，可以证明这样的岛屿是唯一的。 这个岛屿可以是其中某一个海狸的家。

你的任务是找出这 $N$ 座岛屿的连接方式。为了获取信息，你可以问海狸这样一个问题：

实现细节

你的程序在开头需包含头文件 meetings.h，并实现函数：

void Solve(int N)

该函数每个测试点会被调用一次，参数 $N$ 表示岛屿的数量 $N$。

你的程序可以调用函数：

int Query(int u, int v, int w)

表示询问来自岛屿 $u, v, w$ 的海狸聚会的位置岛屿。 参数需要满足 $0 \le u, v, w \le N - 1$ 且 $u \neq v, u \neq w, v \neq w$，否则会被判定为 Wrong Answer [1]。 你的程序运行时调用该函数的次数不能超过 $10^5$ 次，否则会被判定为 Wrong Answer [2]。

void Bridge(int u, int v)

表示你确认了 $u, v$ 间有一座桥。 参数需满足 $0 \le u < v \le N - 1$，否则会被判定为 Wrong Answer [3]。 如果事实上 $u, v$ 间不存在桥，会被判定为 Wrong Answer [4]。 如果一组 $u, v$ 被调用了多次，会被判定为 Wrong Answer [5]。 运行时此函数应被恰被调用 $N - 1$ 次，否则会被判定为 Wrong Answer [6]。

注意事项

你可以定义一些其他的函数和全局变量。

你的程序中不允许进行标准输入输出，但可以通过错误流进行输出。

编译与运行方法

在下发文件中有一个样例评测程序 grader.cpp，假设你的文件是 meetings.cpp，将 grader.cpp、meetings.h、meetings.cpp 放置在同一个目录下，运行：

g++ -std=gnu++14 -O2 -o grader grader.cpp meetings.cpp

会生成一个可执行文件 grader，他通过标准输入输出流进行输入和输出。

---

输入格式

指样例评测程序输入格式。

第一行读入一个正整数 $N$。

接下来 $N - 1$ 行，每行两个整数 $A, B$，表示岛屿 $A, B$ 间有一座桥。

输出格式

指样例评测程序输出格式。

如果你的程序满足要求，输出 Accepted: 100。

如果你的程序被判定为答案错误，输出形如 Wrong Answer [1]。

---

样例

样例输入 1

5
0 1
0 2
1 3
1 4

样例交互

$ \begin{array}{|l|l|} \hline \text{函数调用} & \text{返回值} \\ \hline \text{Solve(5)} & \\ \hline \text{Query(0, 1, 2)} & 0 \\ \hline \text{Query(0, 3, 4)} & 1 \\ \hline \text{Bridge(1, 3)} & \\ \hline \text{Bridge(0, 2)} & \\ \hline \text{Bridge(1, 4)} & \\ \hline \text{Bridge(0, 1)} & \\ \hline \end{array} $

---

数据范围与提示

所有数据满足下列条件。$A_i, B_i$ 的含义参照「样例评测程序输入格式」一节。

$3 \le N \le 2000$

$0 \le A_i, B_i \le N - 1$

保证岛屿之间两两互相可达。

保证每个岛屿至多连出 $18$ 座桥。

子任务

子任务一（$7$） $N \le 7$。

子任务二（$10$） $N \le 50$。

子任务三（$12$） $N \le 300$。

子任务四（$71$） 没有附加限制。设 $X$ 是你在本子任务测试点中进行最多的执行 Query() 的次数。

若 $4 \times 10^4 < X \le 10^5$，则获得 $49$ 的分数。

若 $X \le 4 \times 10^4$，则获得 $71$ 的分数。