P15950 [JOI Final 2026] 电压 2 / Voltage 2
题目描述
**这是一道交互题。本题中，交互库是非自适应的。**
你听说过只是奇特发明有限公司（Just Odd Inventions Co., Ltd.）吗？这家公司只从事奇特的发明。我们将其简称为 JOI。
在 JOI 的一个实验室里，有一个复杂的电路。该电路由 $N$ 个节点和 $M$ 条细电阻器组成。节点编号为 $0$ 到 $N - 1$，电阻器编号为 $0$ 到 $M - 1$。每个节点可以被设置为两种状态之一：**高电压**或**低电压**。电阻器 $i$ ($0 \le i \le M - 1$) 连接节点 $A_i$ 到另一个节点 $B_i$。当且仅当节点 $A_i$ 被设置为高电压且节点 $B_i$ 被设置为低电压时，电流才会流过该电阻器。在所有其他情况下，没有电流流过。此外，对于任意两个节点，无论方向如何，最多只有一条电阻器连接它们。
你是 JOI 的一名研究员，你准备使用这个电路进行一项实验。电路中的电阻器非常细，以至于你无法通过视觉确定它们连接的是哪对节点。然而，有一个线索：在设置电压时，电路的温度会根据流过电流的电阻器数量而升高。因此，在设置电压后，你决定触摸电路并读取其温度。虽然你无法测量电路的精确温度，但你可以进行两次电压设置，并比较哪一次使电路更热。也就是说，通过指定两次电压设置，你可以获得以下信息之一：
* 在第一次电压设置中，流过电流的电阻器数量更多。
* 在两次电压设置中，流过电流的电阻器数量相同。
* 在第二次电压设置中，流过电流的电阻器数量更多。
你的目标是通过重复此类温度比较，确定电路中的所有电阻器，即所有使得从节点 $a$ 到节点 $b$ 存在电阻器的有序对 $(a, b)$。你会预先得知节点数 $N$ 和电阻器数 $M$。你还知道每个电阻器都连接两个不同的节点，且对于任意两个节点，无论方向如何，最多只有一条电阻器连接它们。在这种条件下，根据温度比较获得的信息，确定与电路中电阻器相对应的整套有序对 $(a, b)$。请注意，根据电路的结构，无论进行何种比较或进行多少次比较，可能都无法唯一地确定电阻器。在这种情况下，你必须报告无法唯一地确定它们。
为了防止电阻器损坏，你最多被允许进行 $30000$ 次温度比较。
顺便提一下，JOI 用这个奇怪的电路在做什么样的发明，即使在公司内部也是最高机密，除了社长之外没有人知道。
给定电路中的节点数和电阻器数，编写一个程序，使用最多 $30000$ 次温度比较来确定电路中的电阻器，或者报告这是不可能的。
---
### 实现细节
~~你提交的程序必须使用 `#include` 预处理指令包含 $\texttt{voltage.h}$~~，并且必须实现以下函数。
```cpp
bool solve(int N, int M)
```
* 该函数在每次执行中恰好被调用一次。
* 参数 $N$ 代表电路中的节点数 $N$。
* 参数 $M$ 代表电路中的电阻器数 $M$。
* 如果无论进行何种温度比较或进行多少次比较，都无法唯一确定电阻器连接情况，该函数必须返回 `false`；否则，它必须返回 `true`。
* 如果电阻器连接无法被唯一确定，但该函数返回了 `true`，你的程序将被判定为 **Wrong Answer [1]**。
* 如果电路可以通过温度比较确定，但该函数返回了 `false`，你的程序将被判定为 **Wrong Answer [2]**。
你的程序可以调用以下函数。
```cpp
int query(std::vector x, std::vector y)
```
* 通过使用此函数，你可以进行两次电压设置并比较它们的温度。
* 参数 `x` 指定第一次电压设置，参数 `y` 指定第二次电压设置。
* 参数 `x` 和 `y` 必须是长度为 $N$ 且由 $0$ 和 $1$ 组成的数组。
* 如果 $x[k]$ ($0 \le k \le N - 1$) 为 $1$，则在第一次电压设置中，节点 $k$ 被设置为高电压；如果 $x[k]$ 为 $0$，则节点 $k$ 被设置为低电压。
* 如果 $y[k]$ ($0 \le k \le N - 1$) 为 $1$，则在第二次电压设置中，节点 $k$ 被设置为高电压；如果 $y[k]$ 为 $0$，则节点 $k$ 被设置为低电压。
* 该函数的返回值是电路在第一种和第二种电压设置下温度比较的结果，为 $-1$、$0$ 或 $1$ 之一。
* 如果返回值为 $-1$，则第一次电压设置中流过电流的电阻器数量比第二次多。
* 如果返回值为 $0$，则第一次和第二次电压设置中流过电流的电阻器数量相等。
* 如果返回值为 $1$，则第二次电压设置中流过电流的电阻器数量比第一次多。
* 如果 `x` 的长度不是 $N$，你的程序将被判定为 **Wrong Answer [3]**。
* 如果 `x` 包含 $0$ 或 $1$ 以外的值，你的程序将被判定为 **Wrong Answer [4]**。
* 如果 `y` 的长度不是 $N$，你的程序将被判定为 **Wrong Answer [5]**。
* 如果 `y` 包含 $0$ 或 $1$ 以外的值，你的程序将被判定为 **Wrong Answer [6]**。
* 你调用该函数的次数不得超过 $30000$ 次。如果该函数被调用超过 $30000$ 次，你的程序将被判定为 **Wrong Answer [7]**。
```cpp
void answer(int a, int b)
```
* 使用此函数报告你已识别出的电阻器。
* 参数 `a` 和 `b` 表示存在一个从节点 $a$ 指向节点 $b$ 的电阻器。
* 必须满足 $0 \le a \le N - 1$ 且 $0 \le b \le N - 1$。如果不满足此条件，你的程序将被判定为 **Wrong Answer [8]**。
* 你不得使用相同的参数对 $(a, b)$ 调用此函数两次或更多次。如果违反此条件，你的程序将被判定为 **Wrong Answer [9]**。
* 你调用该函数的次数不得超过 $M$ 次。如果该函数被调用超过 $M$ 次，你的程序将被判定为 **Wrong Answer [10]**。
* 当函数 `solve` 返回 `true` 时，函数 `answer` 必须恰好被调用过 $M$ 次。如果不满足此条件，你的程序将被判定为 **Wrong Answer [11]**。
* 当函数 `solve` 返回 `true` 时，对于到那时为止作为参数传递给 `answer` 的每一对 $(a, b)$，必须确实存在一个从节点 $a$ 指向节点 $b$ 的电阻器。如果不满足此条件，你的程序将被判定为 **Wrong Answer [12]**。
### 注意事项
- 你可以实现额外的辅助函数或声明全局变量以供内部使用。
- 你提交的程序不得使用标准输入/输出或任何其他文件交互。但是，你可以使用标准错误输出进行调试。
### 编译与执行
你可以从竞赛网页下载一个归档文件，其中包含用于测试程序的示例评分器（sample grader）。归档文件中还包含你程序的示例源文件。
示例评分器是文件 $\texttt{grader.cpp}$。要测试你的程序，请将文件 $\texttt{grader.cpp}$、$\texttt{voltage.cpp}$ 和 $\texttt{voltage.h}$ 放在同一目录下，并使用以下命令进行编译：
```bash
g++ -std=gnu++20 -O2 -o grader grader.cpp voltage.cpp
```
或者，你可以通过运行以下命令来执行归档文件中包含的 $\texttt{compile.sh}$ 文件：
```bash
./compile.sh
```
如果编译成功，将生成一个名为 $\texttt{grader}$ 的可执行文件。
请注意，实际的评分器与示例评分器不同。示例评分器作为一个单一进程启动，它将从标准输入读取输入数据并将结果写入标准输出。
输入格式
示例评分器按以下格式从标准输入读取输入：
> $N\ M$\
> $A_0\ B_0$\
> $\vdots$\
> $A_{M-1}\ B_{M-1}$
输出格式
示例评分器将以下信息输出到标准输出（实际输出中不包含引号）。
- 如果你的程序被判定为 **Wrong Answer [3] – [12]** 之一，则会打印错误类型，如“$\texttt{Wrong Answer [5]}$”。
- 否则，将打印对函数 `query` 的调用次数以及函数 `solve` 的返回值，如“$\texttt{Accepted: 30 true}$”。与实际评分器不同，示例评分器不会判断函数 `solve` 的返回值是否正确，即是否应为 **Wrong Answer [1]** 或 **[2]**。
一旦满足 **Wrong Answer [3] – [12]** 中的任何条件，示例评分器就会立即终止执行。如果满足多个错误条件，则仅显示其中之一。
说明/提示
### 评分说明
实际的评分器不是适应性的（non-adaptive）；它从交互开始就有固定的答案。
### 交互示例
以下是示例评分器读取的输入示例以及相应的函数调用。
**输入**
```text
5 6
0 2
2 1
0 3
3 2
3 4
4 1
```
| solve 调用 | 返回值 | 函数调用 | 返回值 |
|------------|--------------|---------------|--------------|
| $\texttt{solve(5,\,6)}$ | | | |
| | | $\texttt{query([0,0,1,1,1], [1,1,1,0,0])}$ | $\texttt{-1}$ |
| | | $\texttt{query([1,0,1,0,0], [0,1,0,1,0])}$ | $\texttt{0}$|
| | | $\texttt{query([0,1,1,1,0], [1,1,0,1,1])}$ | $\texttt{1}$|
| | | $\texttt{answer(0,2)}$ | |
| | | $\texttt{answer(0,3)}$ | |
| | | $\texttt{answer(2,1)}$ | |
| | | $\texttt{answer(3,4)}$ | |
| | | $\texttt{answer(3,2)}$ | |
| | | $\texttt{answer(4,1)}$ | |
| | $\texttt{true}$ | | |
在第一次调用 `query` 时，两次电压设置及流过电流的电阻器如下：
- 在第一种设置中，节点 $0$ 和 $1$ 被设置为低电压，节点 $2$、$3$ 和 $4$ 被设置为高电压。此时，电流流过电阻器 $1$ 和 $5$。
- 在第二种设置中，节点 $3$ 和 $4$ 被设置为低电压，节点 $0$、$1$ 和 $2$ 被设置为高电压。此时，电流流过电阻器 $2$。
由于第一次电压设置中流过电流的电阻器数量较多，返回值为 $\texttt{-1}$。
此示例输入满足子任务 5, 6 的限制。
在从竞赛网站可下载的文件中：$\texttt{sample-01-in.txt}$ 对应于示例输入 1。此外，$\texttt{sample-02-in.txt}$ 满足所有子任务的限制，而 $\texttt{sample-03-in.txt}$ 满足子任务 3, 4, 5, 6 的限制。
### 限制条件
- $2 \le N \le 500$。
- $1 \le M \le 1000$。
- $0 \le A_i \le N-1$ ($0 \le i \le M-1$)。
- $0 \le B_i \le N-1$ ($0 \le i \le M-1$)。
- $A_i \ne B_i$ ($0 \le i \le M-1$)。
- $(A_i, B_i) \ne (A_j, B_j)$ 且 $(A_i, B_i) \ne (B_j, A_j)$ ($0 \le i < j \le M-1$)。
- $N, M, A_i$ 和 $B_i$ 均为整数 ($0 \le i \le M-1$)。
### 子任务
1. (10 分) $N \le 100,\ M = N-1,\ B_i = A_{i+1}$ ($0 \le i \le N-3$)，且 $N$ 个值 $A_0, A_1, \dots, A_{N-2}, B_{N-2}$ 互不相同。
2. (12 分) $M = N-1,\ B_i = A_{i+1}$ ($0 \le i \le N-3$)，且 $N$ 个值 $A_0, A_1, \dots, A_{N-2}, B_{N-2}$ 互不相同。
3. (27 分) $N \le 100,\ A_i \ne A_j$ ($0 \le i < j \le M-1$)。
4. (18 分) $A_i \ne A_j$ ($0 \le i < j \le M-1$)。
5. (17 分) $N \le 100$。
6. (16 分) 无额外限制。