题目背景

请使用 C++ 17 / C++ 20 提交。

不要 #include "thief.h"。在文件头加入以下内容：

#include <vector>
int query(std::vector<int>);
void answer(int,int);

题目描述

这是一道交互题。本题中，交互库可能是自适应的。

有一张 $N$ 个点 $M$ 条边的无向连通图。点编号 $0\sim N-1$，边编号 $0\sim M-1$，第 $i$（$0 \leq i \leq M-1$）条边双向连接点 $U_i$ 和 $V_i$。

有一把钥匙藏在某一个点上，而有一个宝箱藏在另一个节点上。你需要通过至多 $300$ 次询问确定钥匙所在的节点编号和宝箱所在的节点编号：

询问

对于 $i=0,1,\ldots,M-1$，将第 $i$ 条边设置为单向通行。

• 具体地，构造长度为 $M$ 的 $01$ 序列 $x_0\sim x_{M-1}$。$x_i=0$ 表示第 $i$ 条边从 $U_i$ 指向 $V_i$，$x_i=1$ 表示第 $i$ 条边从 $V_i$ 指向 $U_i$。

交互库会返回，在这张图中，是否能从钥匙所在的节点到达宝箱所在的节点。

你需要确定钥匙所在的节点 $A$ 和宝箱所在的节点 $B$。为了获得更高的评分，你需要尽量减少询问次数。

实现细节

你不应该，也不需要实现 main 函数。你应该实现以下的函数：

void solve(int N, int M, std::vector<int> U, std::vector<int> V)

• 该函数每组测试数据仅调用一次。
  • 参数 N 是点数。
  • 参数 M 是边数。
  • 参数 U, V 是长度为 $M$ 的数组，表示边 $i$ 双向连接 $U_i$ 和 $V_i$。

你可以调用以下的函数：

int query(std::vector<int> x)

通过此函数，你可以发起一次询问。

• 参数 x 是一个长度为 $M$ 的数组。对于 $0 \leq i \leq M-1$：
  • 若 x[i] = 0，表示仅允许从点 $U_i$ 到点 $V_i$ 的移动。
  • 若 x[i] = 1，表示仅允许从点 $V_i$ 到点 $U_i$ 的移动。
• 返回值为 $0$ 或 $1$：
  • $0$ 表示无法通过跃迁装置从钥匙所在的点 $A$ 到达宝箱所在的点 $B$。
  • $1$ 表示可以到达。
• 参数 x 的长度必须为 $M$。如果不满足，你的程序将被判为 $\texttt{Wrong Answer [1]}$。
• 参数 x 的每个元素必须是 $0$ 或 $1$。如果不满足，你的程序将被判为 $\texttt{Wrong Answer [2]}$。
• 调用 query 函数的次数不得超过 $300$ 次。如果超过，你的程序将被判为 $\texttt{Wrong Answer [3]}$。

void answer(int A, int B)

你需调用此函数来提交答案，即钥匙所在的点 $A$ 和宝箱所在的点 $B$。

• 参数 A 表示钥匙藏在点 $A$ 中。
• 参数 A 必须在 $0$ 到 $N-1$ 的范围内（两边取等）。如果不满足，你的程序将被判为 $\texttt{Wrong Answer [4]}$。
• 参数 B 表示宝箱藏在点 $B$ 中。
• 参数 B 必须在 $0$ 到 $N-1$ 的范围内（两边取等）。如果不满足，你的程序将被判为 $\texttt{Wrong Answer [5]}$。
• 如果提交的答案错误，你的程序将被判为 $\texttt{Wrong Answer [6]}$。
• answer 函数必须被恰好调用一次。如果多次调用，你的程序将被判为 $\texttt{Wrong Answer [7]}$。当 solve 函数终止时，如果未调用 answer 函数，你的程序将被判为 $\texttt{Wrong Answer [8]}$。

注意事项

• 你的程序可以定义其他函数或使用全局变量。
• 你的程序不得使用标准输入输出，也不得通过任何方式与其他文件通信。但允许将调试信息输出到标准错误流。
• 对于部分测试点，交互库是自适应的。这意味着交互库在开始时没有固定答案，而是根据之前对 query 函数的调用历史来响应。保证至少存在一个答案与交互库的所有回答不矛盾。

测试运行

你可以从附件中下载包含 Sample Grader 的压缩包。该压缩包还包含一个示例源文件。

Sample Grader 是文件 grader.cpp。

要测试你的程序，请将 grader.cpp、thief.cpp、thief.h 放在同一目录下，并运行以下命令进行编译：

g++ -std=gnu++20 -O2 -o grader grader.cpp thief.cpp  

或者，你可以运行压缩包中的 compile.sh 脚本。此时，使用以下命令进行编译：

./compile.sh  

当编译成功时，会生成可执行文件 grader。注意，实际评测程序与Sample Grader 不同。Sample Grader 会作为单个进程运行，从标准输入读取数据并将结果写入标准输出。

输入格式

Sample Grader 输入格式如下所示：

$N$ $M$ $A$ $B$
$U_0$ $V_0$
$U_1$ $V_1$
$\vdots$
$U_{M-1}$ $V_{M-1}$

输出格式

Sample Grader 输出格式如下：

• 如果你的程序被判为正确，会报告调用 query 函数的次数，例如 $\texttt{Accepted: 25}$。
• 如果你的程序被判为任何类型的错误答案，Sample Grader 会写出错误类型，例如$\texttt{Wrong Answer [4]}$。
  如果你的程序满足多种错误类型的条件，Sample Grader 只会报告其中一种。当某一错误条件触发时，Sample Grader 可能直接终止执行。

5 4 0 4
0 1
0 3
1 2
1 4

Accepted: 4

提示

样例交互

交互库调用	选手程序调用	返回值
$\texttt{solve(5, 4, [0, 0, 1, 1], [1, 3, 2, 4])}$	$$
	$\texttt{query([0, 1, 0, 0])}$	$1$
	$\texttt{query([1, 1, 1, 0])}$	$0$
	$\texttt{query([0, 0, 1, 0])}$	$1$
	$\texttt{query([0, 0, 1, 1])}$	$0$
	$\texttt{answer(0, 4) }$

• 第 $1$ 次调用 query 函数：
  • 边 $0$：仅允许从点 $0$ 到点 $1$。
  • 边 $1$：仅允许从点 $3$ 到点 $0$。
  • 边 $2$：仅允许从点 $1$ 到点 $2$。
  • 边 $3$：仅允许从点 $1$ 到点 $4$。
    在此设置下，可以通过边 $0 \to 3$ 的顺序从点 $0$ 到达点 $4$，因此返回值为 $1$。
• 第 $2$ 次调用 query 函数：
  • 边 $0$：仅允许从点 $1$ 到点 $0$。
  • 边 $1$：仅允许从点 $3$ 到点 $0$。
  • 边 $2$：仅允许从点 $2$ 到点 $1$。
  • 边 $3$：仅允许从点 $1$ 到点 $4$。
    在此设置下，无法从点 $0$ 到达点 $4$，因此返回值为 $0$。
• 第 $3$ 次调用 query 函数：
  • 边 $0$：仅允许从点 $0$ 到点 $1$。
  • 边 $1$：仅允许从点 $0$ 到点 $3$。
  • 边 $2$：仅允许从点 $2$ 到点 $1$。
  • 边 $3$：仅允许从点 $1$ 到点 $4$。
    在此设置下，可以通过跃迁装置到达点 $4$，因此返回值为 $1$。
• 第 $4$ 次调用 query 时，无法从点 $0$ 到达 4，返回值为 $0$。

最终调用 answer(0, 4) 提交答案，表示钥匙在点 $0$、宝箱在点 $4$。

此样例输入满足子任务 $3\sim 8$ 的约束条件。竞赛网页提供的 sample-01-in.txt 文件对应此样例。

压缩包中的示例程序源码的函数调用与本示例一致。

数据范围

• $2 \leq N \leq 10\,000$；
• $1 \leq M \leq 15\,000$；
• $0 \leq A \leq N-1$；
• $0 \leq B \leq N-1$；
• $A \neq B$；
• $0 \leq U_i \lt V_i \leq N-1$（$0 \leq i \leq M-1$）；
• $(U_i, V_i) \neq (U_j, V_j)$（$0 \leq i \lt j \leq M-1$）；
• 可以通过跃迁装置从任意点到达其他任意点。

子任务 与 计分方式

• $\text{Subtask 1 (7 pts)}$：$M = N - 1$，且 $U_i = i,V_i = i + 1$（$0 \leq i \leq M - 1$）。
• $\text{Subtask 2 (13 pts)}$： $M = N - 1$，且 $U_i = 0,V_i = i + 1$（$0 \leq i \leq M - 1$）。
• $\text{Subtask 3 (2 pts)}$：$M = N - 1$，且 $N \leq 8$。
• $\text{Subtask 4 (8 pts)}$：$M = N - 1$，且 $N \leq 50$。
• $\text{Subtask 5 (5 pts)}$：$M = N - 1$，且 $N \leq 150$。
• $\text{Subtask 6 (5 pts)}$：$M = N - 1$，且 $N \leq 250$。
• $\text{Subtask 7 (40 pts)}$： $M = N - 1$。 在此子任务中，评分规则如下：
  • 如果子任务 $7$ 中任意测试用例被判为 $\text{Wrong Answer}$，或运行超时、内存超限、运行错误，则该子任务得 $0$ 分。
  • 否则，令 $T$ 表示本子任务所有测试用例中 query 函数调用次数的最大值。评分规则为：
    • 若 $120 < T$，得 20 分。
    • 若 $70 < T \leq 120$，得 30 分。
    • 若 $T \leq 70$，得 40 分。
• $\text{Subtask 8 (20 pts)}$：无额外限制。 在此子任务中，评分规则如下：
  • 如果子任务 $8$ 中任意测试用例被判为 $\text{Wrong Answer}$，或运行超时、内存超限、运行错误，则该子任务得 $0$ 分。
  • 否则，令 $T$ 表示本子任务所有测试用例中 query 函数调用次数的最大值。评分规则为：
    • 若 $120 < T$，得 10 分。
    • 若 $70 < T \leq 120$，得 15 分。
    • 若 $T \leq 70$，得 20 分。

子任务 $1\sim 6$ 的得分与 query 的调用次数无关（只要不超过 $300$ 次）。

对于部分测试点，交互库是自适应的。这意味着交互库在开始时没有固定答案，而是根据之前对 query 函数的调用历史来响应。保证至少存在一个答案与交互库的所有回答不矛盾。