题目描述

有 $N$ 个海狸居住的岛屿，编号从 $0$ 到 $N-1$。这些岛屿由 $N-1$ 座双向桥梁连接。可以通过一些桥梁在任意两个岛屿之间通行。对于每个岛屿，最多有 $18$ 座桥梁直接与其相连。每个岛屿上居住着一只海狸。

有时，一些海狸会在某个岛屿上聚集开会。当恰好三只海狸相遇时，它们会在以下岛屿上聚集：

使这三只海狸在聚集过程中经过的桥梁总数最少的岛屿（这样的岛屿是唯一的）。

请注意，该岛屿可能与其中一只海狸所居住的岛屿重合。

你对这 $N$ 个岛屿如何通过桥梁连接感兴趣。你无法直接前往并检查岛屿，因此你将向海狸发出一些指令。每条指令如下：

• 你指定三个岛屿 $u$、$v$ 和 $w$（$0 \le u \le N-1$，$0 \le v \le N-1$，$0 \le w \le N-1$，$u \ne v$，$u \ne w$，$v \ne w$），并让居住在岛屿 $u$、$v$ 和 $w$ 上的海狸召开会议。
• 然后，你可以看到三只海狸聚集的岛屿。

你希望用尽可能少的指令确定岛屿之间的连接方式。

编写一个程序，在给定岛屿数量并和海狸通信后，确定岛屿之间的连接方式。

实现细节

这是一道交互题。你需要实现这一个函数：

• void Solve(int N)
  • 此函数在每个测试用例中被调用且仅调用一次。
  • 参数 $N$ 表示岛屿的数量 $N$。

你的程序可以调用以下函数：

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

  • 此函数返回你指定的三个岛屿索引所对应的海狸聚集开会的岛屿的索引。
  • 你通过参数 $u$、$v$ 和 $w$ 分别指定三个岛屿的索引。这些值必须满足 $0 \le u \le N-1$、$0 \le v \le N-1$、$0 \le w \le N-1$，且 $u \ne v$、$u \ne w$、$v \ne w$。否则，你的程序将被视为 Wrong Answer [1]。
  • 函数 Query 的调用次数不得超过 $100\,000$ 次。否则，你的程序将被视为 Wrong Answer [2]。

• void Bridge(int u, int v)

  • 使用此函数，你需回答岛屿之间如何通过桥梁连接。
  • 参数 $u$ 和 $v$ 表示岛屿 $u$ 和 $v$ 通过一座桥梁直接相连。
  • 若 $0 \le u < v \le N-1$ 不成立，你的程序将被视为 Wrong Answer [3]。
  • 若岛屿 $u$ 和 $v$ 并未通过桥梁直接相连，你的程序将被视为 Wrong Answer [4]。
  • 若函数 Bridge 以相同的参数 $u$ 和 $v$ 被多次调用，你的程序将被视为 Wrong Answer [5]。
  • 由于共有 $N-1$ 座桥梁，函数 Bridge 必须被调用恰好 $N-1$ 次。若在函数 Solve 执行结束时，对函数 Bridge 的调用次数不等于 $N-1$，你的程序将被视为 Wrong Answer [6]。

编译与测试运行

示例评测器是文件 grader.cpp。为了测试你的程序，请将 grader.cpp、meetings.cpp 和 meetings.h 放在同一目录下，并运行以下命令来编译你的程序：

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

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

请注意，在洛谷上提交代码时，不应引入头文件 meetings.h，而是应当加入这两行代码，并且选择不低于 C++17 的语言版本提交：

int Query(int u, int v, int w);
void Bridge(int u, int v);

输入格式

示例评测器从标准输入读取以下数据：

$N$

$A_0\ B_0$

$\vdots$

$A_{N-2}\ B_{N-2}$

其中，$A_i$ 和 $B_i$（$0 \le i \le N-2$）表示岛屿 $A_i$ 和 $B_i$ 通过一座桥梁直接相连。

输出格式

当程序成功终止时，示例评测器将以下信息写入标准输出（引号仅用于清晰说明）：

• 若你的程序被视为正确，它将输出函数 Query 的调用次数，格式为 “Accepted: 100”。
• 若你的程序被视为 Wrong Answer，它将输出其类型，格式为 “Wrong Answer [1]”。

若你的程序被判定为多种类型的 Wrong Answer，示例评测器仅报告其中一种。

5
0 1
0 2
1 3
1 4

提示

样例 1 解释

调用		返回值
Solve(5)
	Query(0, 1, 2)	0
	Query(0, 3, 4)	1
	Bridge(1, 3)
	Bridge(0, 2)
	Bridge(1, 4)
	Bridge(0, 1)

数据范围

有关 $A_i$ 和 $B_i$ 的定义，请参阅“示例评测器的输入”部分。

• $3 \le N \le 2000$。
• $0 \le A_i < B_i \le N-1$（$0 \le i \le N-2$）。
• 可以通过若干座桥梁在任意两个岛屿之间通行。
• 对于每个岛屿，最多有 $18$ 座桥梁直接与其相连。