题目描述

题目译自 JOISC 2025 Day2 T3 「宇宙怪盗 / Space Thief」

在 JOI 银河中，你是一位声名赫赫的怪盗。JOI 银河拥有 $N$ 个星球，编号从 $0$ 到 $N-1$，还有 $M$ 个传送装置，编号从 $0$ 到 $M-1$。每个传送装置 $i$ $(0 \leq i \leq M-1)$ 双向连接星球 $U_i$ 和 $V_i$，且任意两颗星球间都能通过若干传送装置到达。

某颗星球藏着一把钥匙，另一颗藏着宝箱。你的任务是找出钥匙所在的星球编号 $A$ 和宝箱所在的星球编号 $B$。为此，你最多可以进行 $300$ 次提问：

• 对每个传送装置 $i$ $(0 \leq i \leq 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$ 的数组，U[i] 和 V[i] 表示传送装置 $i$ 双向连接的星球编号 $U_i$ 和 $V_i$。

在 thief.cpp 中可调用以下函数：

• int query(std::vector<int> x)
  • 用于提问。
  • 参数 x 是长度为 $M$ 的数组，对于 $0\leq i\leq M-1$，x[i] 为 $0$ 表示装置 $i$ 从 $U_i$ 到 $V_i$ 单向连接，x[i] 为 $1$ 表示从 $V_i$ 到 $U_i$ 单向连接。
  • 返回值为 $0$ 表示无法从 $A$ 到 $B$，$1$ 表示可行。
  • 约束：
    • x 长度必须为 $M$，否则判为 Wrong Answer [1]。
    • x 各元素须为 $0$ 或 $1$，否则判为 Wrong Answer [2]。
    • 调用次数不得超 $300$，否则判为 Wrong Answer [3]。
• void answer(int A, int B)
  • 提交答案。
  • 参数 A 是钥匙星球编号，需满足 $0 \leq A \leq N-1$，否则判为 Wrong Answer [4]。
  • 参数 B 是宝箱星球编号，需满足 $0 \leq B \leq N-1$，否则判为 Wrong Answer [5]。
  • 若 A 或 B 错误，判为 Wrong Answer [6]。
  • 必须调用恰好一次，多于一次判为 Wrong Answer [7]，未调用判为 Wrong Answer [8]。

注意事项

• 可自由定义其他函数或全局变量。
• 程序不得与标准输入输出或其他文件交互，但可输出调试信息到标准错误流。

部分测试点为自适应评测，即答案非固定，随 query 调用动态调整，但保证存在至少一种一致解。

编译与运行

「文件」界面提供示例评测程序的压缩包，包含 grader.cpp 和样例文件。测试时，将 grader.cpp、thief.cpp、thief.h 置于同一目录，运行：

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

或使用 compile.sh：

./compile.sh

成功后生成 grader 可执行文件。注意：实际评测程序与示例不同，示例为单进程，从标准输入读取，输出到标准输出。

输入格式

第一行包含四个整数 $N,M,A,B$。

接下来 $M$ 行，每行包含两个整数 $U_i,V_i$。

输出格式

输出到标准输出：

• 正确：输出 query 调用次数，如 Accepted: 25。
• 错误：输出类型，如 Wrong Answer [4]。若有多重错误，仅显示一种，可能提前终止。

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

第 $1$ 次 query 函数调用的选择如下：

• 传送装置 $0$：从星球 $0$ 到星球 $1$ 单向连接。
• 传送装置 $1$：从星球 $3$ 到星球 $0$ 单向连接。
• 传送装置 $2$：从星球 $1$ 到星球 $2$ 单向连接。
• 传送装置 $3$：从星球 $1$ 到星球 $4$ 单向连接。 在此设置下，可以通过传送装置 $0, 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$ 单向连接。 在此设置下，可以通过传送装置从星球 $0$ 移动到星球 $4$，因此返回值为 $1$。

第 $4$ 次 query 函数调用的选择下，无法通过传送装置从星球 $0$ 移动到星球 $4$，因此返回值为 $0$。

answer 函数调用表示回答藏有钥匙的星球为 $0$，藏有宝箱的星球为 $4$。

此样例满足子任务 $3,4,5,6,7,8$ 的限制，对应 sample-01-in.txt。

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 10000$
• $1 \leq M \leq 15000$
• $0 \leq A \leq N-1$
• $0 \leq B \leq N-1$
• $A \neq B$
• $0 \leq U_i < V_i \leq N-1$ $(0 \leq i \leq M-1)$
• $(U_i, V_i) \neq (U_j, V_j)$ $(0 \leq i < j \leq M-1)$
• 任意两星球间可通过若干传送装置连通

详细子任务附加限制及分值如下表所示。

子任务 $1$ 至 $6$ 得分不根据 query 次数（$\leq 300$ 即可），但超 $70$ 次可能显示 Partially Correct。