你在 JOI 星系中是一名窃贼。
JOI 星系中有 $N$ 颗恒星，编号为 $0$ 到 $N - 1$。星系中还有 $M$ 个跃迁装置，编号为 $0$ 到 $M - 1$。跃迁装置 $i$ ($0 \le i \le M - 1$) 连接恒星 $U_i$ 和恒星 $V_i$，且是双向的。通过使用跃迁装置，可以从任意一颗恒星前往任意另一颗恒星。
一把钥匙藏在某颗恒星中，一个宝箱藏在另一颗恒星中。你的任务是确定钥匙所在的恒星编号和宝箱所在的恒星编号。为了完成任务，你可以进行最多 300 次如下询问：
- 设定每个跃迁装置的方向。具体来说，对于每个跃迁装置 $i$ ($0 \le i \le M - 1$)，选择以下其中一种：
- 仅允许从恒星 $U_i$ 前往恒星 $V_i$。
- 仅允许从恒星 $V_i$ 前往恒星 $U_i$。
- 在这些条件下，询问是否可以通过跃迁装置从藏有钥匙的恒星前往藏有宝箱的恒星。
你需要确定钥匙所在的恒星 $A$ 和宝箱所在的恒星 $B$ 的编号。为了获得更高的评价，你需要减少询问次数。
给定星系的信息，编写一个程序，通过提问来确定钥匙所在的恒星 $A$ 和宝箱所在的恒星 $B$。
实现细节
你需要提交一个文件。
文件名为 thief.cpp。它应该实现以下函数。程序应使用预处理指令 #include 包含 thief.h。
void solve(int N, int M, std::vector<int> U, std::vector<int> V)该函数对每个测试用例仅调用一次。- 参数 $N$ 是恒星的数量 $N$。
- 参数 $M$ 是跃迁装置的数量 $M$。
- 参数 $U, V$ 是长度为 $M$ 的数组。对于每个 $i$ ($0 \le i \le M - 1$)，$U[i]$ 和 $V[i]$ 表示由跃迁装置 $i$ 双向连接的恒星 $U_i$ 和 $V_i$。
在 thief.cpp 中，你的程序可以调用以下函数：
int query(std::vector<int> x)使用此函数进行询问。- 参数 $x$ 是一个长度为 $M$ 的数组。对于 $0 \le i \le M - 1$：
- 如果 $x[i] = 0$，表示仅允许从恒星 $U_i$ 前往恒星 $V_i$。
- 如果 $x[i] = 1$，表示仅允许从恒星 $V_i$ 前往恒星 $U_i$。
- 返回值为 $0$ 或 $1$：
- $0$ 表示在当前条件下，无法通过跃迁装置从恒星 $A$ 前往恒星 $B$。
- $1$ 表示在当前条件下，可以通过跃迁装置从恒星 $A$ 前往恒星 $B$。
- 参数 $x$ 的长度必须为 $M$。如果不是，你的程序将被判为 Wrong Answer [1]。
- 参数 $x$ 的每个元素必须为 $0$ 或 $1$。如果不是，你的程序将被判为 Wrong Answer [2]。
- 调用
query函数的次数不得超过 300 次。如果超过 300 次，你的程序将被判为 Wrong Answer [3]。
- 参数 $x$ 是一个长度为 $M$ 的数组。对于 $0 \le i \le M - 1$：
void answer(int A, int B)调用此函数来回答钥匙所在的恒星 $A$ 和宝箱所在的恒星 $B$ 的编号。- 参数 $A$ 表示钥匙藏在恒星 $A$ 中。
- 参数 $A$ 必须在 $0$ 到 $N - 1$ 之间（包含边界）。如果不是，你的程序将被判为 Wrong Answer [4]。
- 参数 $B$ 表示宝箱藏在恒星 $B$ 中。
- 参数 $B$ 必须在 $0$ 到 $N - 1$ 之间（包含边界）。如果不是，你的程序将被判为 Wrong Answer [5]。
- 如果你回答了错误的编号，你的程序将被判为 Wrong Answer [6]。
answer函数应恰好调用一次。如果调用超过一次，你的程序将被判为 Wrong Answer [7]。当solve函数终止时，如果未调用answer函数，你的程序将被判为 Wrong Answer [8]。
重要提示
- 你的程序可以实现其他内部函数或使用全局变量。
- 你的程序不得使用标准输入和标准输出。你的程序不得以任何方式与其他文件通信。但是，你的程序可以将调试信息输出到标准错误。
数据范围
所有输入数据满足以下条件：
- $2 \le N \le 10\,000$。
- $1 \le M \le 15\,000$。
- $0 \le A \le N - 1$。
- $0 \le B \le N - 1$。
- $A \neq B$。
- $0 \le U_i < V_i \le N - 1$ ($0 \le i \le M - 1$)。
- $(U_i, V_i) \neq (U_j, V_j)$ ($0 \le i < j \le M - 1$)。
- 通过使用跃迁装置，可以从任意一颗恒星前往任意另一颗恒星。
子任务
- (7 分) $M = N - 1$，$U_i = i$，$V_i = i + 1$ ($0 \le i \le M - 1$)。
- (13 分) $M = N - 1$，$U_i = 0$，$V_i = i + 1$ ($0 \le i \le M - 1$)。
- (2 分) $M = N - 1$，$N \le 8$。
- (8 分) $M = N - 1$，$N \le 50$。
- (5 分) $M = N - 1$，$N \le 150$。
- (5 分) $M = N - 1$，$N \le 250$。
- (40 分) $M = N - 1$。在此子任务中，得分如下：
- 如果子任务 7 中的任何测试用例被判为 Wrong Answer，或超过时间限制、内存限制，或遇到运行时错误，则子任务得分为 0 分。
- 否则，令 $T$ 为该子任务所有测试用例中调用
query函数次数的最大值。得分如下：- $120 < T$ 时得 20 分。
- $70 < T \le 120$ 时得 30 分。
- $T \le 70$ 时得 40 分。
- (20 分) 无额外限制。在此子任务中，得分如下：
- 如果子任务 8 中的任何测试用例被判为 Wrong Answer，或超过时间限制、内存限制，或遇到运行时错误，则子任务得分为 0 分。
- 否则，令 $T$ 为该子任务所有测试用例中调用
query函数次数的最大值。得分如下：- $120 < T$ 时得 10 分。
- $70 < T \le 120$ 时得 15 分。
- $T \le 70$ 时得 20 分。
子任务 1, 2, 3, 4, 5, 6 的得分不取决于 query 函数的调用次数，只要不超过 300 次即可。然而，当次数超过 70 时，竞赛系统可能会显示“输出部分正确”。
样例
样例 1
5 4 0 4 solve(5, 4, [0, 0, 1, 1], [1, 3, 2, 4]) query([0, 1, 0, 0]) -> 1 query([1, 1, 1, 0]) -> 0 query([0, 0, 1, 0]) -> 1 query([0, 0, 1, 1]) -> 0 answer(0, 4)