有 $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 \neq v, u \neq w, v \neq w$)，并让居住在岛屿 $u, v$ 和 $w$ 的海狸举行会议。 然后，你可以看到这三只海狸聚集的岛屿。

你希望通过较少的指令确定岛屿是如何连接的。 编写一个程序，在给定岛屿数量的情况下，通过与海狸交流，确定岛屿是如何连接的。

实现细节

你需要提交一个文件。 文件名应为 meetings.cpp。它应该实现以下函数。程序应包含 meetings.h。

• void Solve(int 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 \neq v, u \neq w$ 且 $v \neq 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。 注意，实际的评测程序与示例评测程序不同。示例评测程序将作为一个单一进程执行，它将从标准输入读取输入数据并将结果写入标准输出。

输入格式

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

$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，示例评测程序仅报告其中一种。

数据范围

请参考“输入格式”部分中关于 $A_i$ 和 $B_i$ 的定义。

• $3 \le N \le 2\,000$。
• $0 \le A_i < B_i \le N - 1$ ($0 \le i \le N - 2$)。
• 通过一些桥梁可以在任意岛屿之间通行。
• 对于每个岛屿，最多有 $18$ 座桥梁直接连接到它。

子任务

1. ($7$ 分) $N \le 7$。
2. ($10$ 分) $N \le 50$。
3. ($12$ 分) $N \le 300$。

4. ($71$ 分) 无附加限制。

5. 对于子任务 1、2 和 3，如果你的程序对子任务中的所有测试用例都正确，你将获得满分。

6. 对于子任务 4，如果你的程序对所有测试用例都正确，你的得分将如下所示，其中 $X$ 是单个测试用例中调用函数 Query 的最大次数：
   • 如果 $40\,000 < X \le 100\,000$，得 $49$ 分。
   • 如果 $X \le 40\,000$，得 $71$ 分。

样例

以下是示例评测程序的输入示例及相应的函数调用。

样例输入 1

5
0 1
0 2
1 3
1 4

样例输出 1

Accepted: 2

说明