你知道 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)$ 的完整集合。注意，根据电路的结构，无论执行什么比较或执行多少次比较，可能都无法唯一地确定电阻。在这种情况下，你必须报告无法唯一确定它们。
为了防止电阻损坏，你最多允许进行 $30\,000$ 次温度比较。
顺便提一下，JOI 用这个奇怪的电路在做什么发明，即使在公司内部也是绝密，除了总裁之外没有人知道。
给定电路中的节点数和电阻数，编写一个程序，确定电路中的电阻，或者报告这是不可能的，且最多使用 $30\,000$ 次温度比较。
实现细节
你提交的程序必须使用 #include 预处理指令包含 voltage.h，并必须实现以下函数。
bool solve(int N, int M)- 此函数在每次执行中被调用且仅被调用一次。
- 参数
N表示电路中的节点数 $N$。 - 参数
M表示电路中的电阻数 $M$。 - 如果无论执行什么温度比较或执行多少次比较都无法唯一确定电阻连接，则此函数必须返回
false；否则，它必须返回true。 - 如果此函数在无法唯一确定电阻连接时返回
true，你的程序将被判定为 Wrong Answer [1]。 - 如果此函数在可以从温度比较中确定电路的情况下返回
false，你的程序将被判定为 Wrong Answer [2]。
你的程序可以调用以下函数。
int query(std::vector<int> x, std::vector<int> 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]。 - 你调用此函数的次数不得超过 $30\,000$ 次。如果调用次数超过 $30\,000$ 次，你的程序将被判定为 Wrong Answer [7]。
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]。
说明
- 你可以实现额外的辅助函数或声明全局变量以供内部使用。
- 你提交的程序不得使用标准输入/输出或任何其他文件交互。但是，你可以使用标准错误输出进行调试。
数据范围
- $2 \le N \le 500$
- $1 \le M \le 1\,000$
- $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 \neq B_i$ ($0 \le i \le M - 1$)
- $(A_i, B_i) \neq (A_j, B_j)$ 且 $(A_i, B_i) \neq (B_j, A_j)$ ($0 \le i < j \le M - 1$)
- $N, M, A_i, B_i$ 均为整数 ($0 \le i \le M - 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}$ 互不相同。
- (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}$ 互不相同。
- (27 分) $N \le 100, A_i \neq A_j$ ($0 \le i < j \le M - 1$)。
- (18 分) $A_i \neq A_j$ ($0 \le i < j \le M - 1$)。
- (17 分) $N \le 100$。
- (16 分) 无附加限制。
样例
样例输入 1
5 6 0 2 2 1 0 3 3 2 3 4 4 1
样例输出 1
solve(5, 6) query([0,0,1,1,1], [1,1,1,0,0]) -> -1 query([1,0,1,0,0], [0,1,0,1,0]) -> 0 query([0,1,1,1,0], [1,1,0,1,1]) -> 1 answer(0,2) answer(0,3) answer(2,1) answer(3,4) answer(3,2) answer(4,1) true
说明
在第一次调用 query 时，两次电压设置以及流过电流的电阻如下：
在第一次设置中，节点 $0$ 和 $1$ 被设置为低电压，节点 $2, 3, 4$ 被设置为高电压。此时，电流流过电阻 $1$ 和 $5$。
在第二次设置中，节点 $3$ 和 $4$ 被设置为低电压，节点 $0, 1, 2$ 被设置为高电压。此时，电流流过电阻 $2$。
由于第一次电压设置中流过电流的电阻数量较多，因此返回值为 $-1$。
此样例输入满足子任务 5 和 6 的约束。