这是一道交互题。
出题人 02 喜欢网上冲浪。可是这天，他所在的小区的网络坏掉了，于是他喊来了你帮忙修一修。
小区的网络由 $N$ 个网络结点和 $M$ 条信道组成，可以被看作是一张 $N$ 个点 $M$ 条边的无向简单图（简单图满足任意两点之间至多存在一条直接相连的边，且没有自环）。点从 $1 \sim N$ 编号，边从 $1 \sim M$ 编号。目前，你只知道信道的总数是 $M$，并且还掌握着每条信道的管理权限，然而你并不知道每条信道连接着哪两个结点。
为了恢复出网络结构，你可以使用一种土办法：重启大法！
当然重启也是需要智慧的。具体来说，你可以进行若干次操作，每次操作方式如下：
- 给每个结点 $i$ 标上一个自己定的权值 $a_i$；
- 选取一个信道的子集 $S$，把不在 $S$ 里的信道都关闭，只让 $S$ 里的信道保持开启状态；
- 此时，每个结点 $i$ 会自动计算出与 $i$ 通过开启状态的信道直接相邻的所有点 $v$ 的 $a_v$ 异或和，记为 $b_i$；
- 你通过管理员权限获取所有结点的 $b_i$ 值，然后关闭的信道都重启，网络恢复至原状。
请你在不超过 $50$ 次操作内，求出所有信道构成的集合。
注意，你只需要求出信道的集合。即，你只需要恢复出哪些结点之间有信道，不用恢复出每条信道对应的编号。
实现细节
你不需要，也不应该实现主函数，你只需要实现函数 $\texttt{Solve(N, M)}$，这里的 $\texttt{N}$ 和 $\texttt{M}$ 分别表示结点和信道的个数。你可以通过调用如下函数来和交互库进行交互：
- $\texttt{Query(A,S)}$
- 这个函数可以暂时删去编号不在 $S$ 中的信道，并将 $i$ 号点的 $a_i$ 设置成 $A[i-1]$；
- 交互库会返回一个大小为$N$的
vector$B$，$B[i-1]$ 表示 $i$ 号点的 $b_i$； - 你需要保证 对 $S$ 中的任意元素 $x$，有 $1 \le x \le M$且互不相同，同时你需要保证 $A$ 的大小恰好为$N$；
- $A, S, B$ 均为
vector； - $A, B$ 中元素类型为
unsigned long long，$S$中元素类型为int。
- $\texttt{Report(x, y)}$
- 这个函数可以向交互库汇报一条你发现的连接 $x$ 和 $y$ 的信道；
- 你需要保证 $1 \le x,y \le N$；
- $x,y$ 均为
int； - 你必须恰好将所有信道报告一次，否则你的程序将会判定为错误。
评测时，交互库会恰好调用 $\texttt{Solve}$ 一次。
本题保证所使用的图在交互开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定性的，你不需要关心这些操作在交互库中的具体实现。
生成数据时，图是按一定方式从 $N$ 个点，$M$ 条边的简单无向图中随机选取的（见限制与约定一节）。
数据保证在调用次数限制下，交互库运行所需的时间不超过 2.5s；交互库使用的内存大小固定，且不超过 128MB。
实现方法
本题仅支持 C++ 语言。
附加文件中已经提供了一个 template_explore.cpp，请将这个文件拷贝一份，重命名为 explore.cpp，然后在其基础上答题。
- 请确保你的程序开头有
#include "explore.h"。 - 你需要实现的函数 $\texttt{Solve}$ 的接口信息如下：
void Solve(int N, int M);
- 你可以调用的交互函数的接口如下：
vector<unsigned long long> Query(vector<unsigned long long> A, vector<int> S);void Report(int x,int y);
测试程序方式
试题目录下的 grader.cpp 是我们提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。
- 编译方法：
- 你需要在本题目录下使用如下命令编译得到可执行程序：
g++ grader.cpp explore.cpp -o explore -O2 -lm
- 你需要在本题目录下使用如下命令编译得到可执行程序：
- 对于编译得到的可执行程序：
- 可执行文件将从标准输入读入以下格式的数据：
- 第一行包含两个整数 $N, M$，意义如题面描述。
- 接下来 $M$ 行，每行两个整数 $x, y$，描述一条连接 $x$ 号点与 $y$ 号点的无向边。
- 读入完成之后，交互库将调用恰好一次函数 $\texttt{Solve}$，用输入的数据测试你的函数。你的函数正确返回后，交互库会判断你的计算是否正确，若正确则会输出
Correct，否则会输出相应的错误信息。
- 可执行文件将从标准输入读入以下格式的数据：
假设可执行文件读入的数据为：
3 2
1 2
2 3数据第一行的两个整数分别表示点数和边条数，即 $N = 3 , M = 2$。
$\texttt{Query(S, A)}$ 调用次数不能超过 50 次。
下面是一个正确的交互过程：
| 选手程序 | 交互库 | 说明 |
|---|---|---|
| 调用 $\texttt{Solve(3, 2)}$ | 开始测试 | |
| 调用 $\texttt{Query}(\{1,2,4\},\{1\})$ | 返回 $\{2,1,0\}$ | $1$ 号节点权值为 $a[2]=2$, $2$号节点权值为$a[1]=1$, $3$号节点权值为$0$ |
| 调用 $\texttt{Query}(\{1,2,4\},\{1,2\})$ | 返回 $\{2,5,2\}$ | $1$ 号节点权值为 $a[2]=2$, $2$号节点权值为$a[1] \mathbin{\mathrm{xor}} a[3]=5$, $3$号节点权值为$a[2]=2$ |
| 调用 $\texttt{report}(1, 2)$ | 发现了信道 $(1, 2)$ 并记录 | |
| 调用 $\texttt{report}(3, 2)$ | 发现了信道 $(3, 2)$ 并记录 | |
| 运行结束并返回 | 向屏幕打印 Correct | 交互结束，结果正确 |
样例一
见附加文件下载
样例二
见附加文件下载
评分方式
最终评测只会收取 explore.cpp，修改选手目录下其他文件对评测无效。
本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。
在上述条件基础上，在一个测试点中，你得到满分，当且仅当：
- 你的每次函数调用均合法，且调用 $\texttt{Query},\texttt{Report}$ 的次数分别不超过 $50$，$M$ 次。
- 由于 $\texttt{Report}$ 的调用次数限制为 $M$，你的每次调用都必须记录一条新的且存在的边；即每次调用 $\texttt{report(x, y)}$ 时，应满足：有一条连接 $x$ 号点和 $y$ 号点的路径，且在这次调用之前从未调用过 $\texttt{report(x, y)}$ 或 $\texttt{report(y, x)}$。
- 你实现的函数 $\texttt{Solve}$ 正常返回。
- 在 $\texttt{Solve}$ 函数返回时，你已经通过调用 $\texttt{Report}$ 记录了全部 $M$ 条信道。
限制与约定
| 测试点编号 | $N$ | $M$ | 特殊性质 |
|---|---|---|---|
| $1$ | $N=20$ | $M=50$ | 无 |
| $2$ | $N=60$ | $M=300$ | |
| $3$ | $N=3000$ | $M=10000$ | |
| $4$ | $N=6000$ | $M=30000$ | |
| $5$ | $N=49998$ | $M=49997$ | 图为连通图 |
| $6$ | $N=49999$ | $M=49999$ | |
| $7$ | $N=50000$ | $M=50000$ | 无 |
| $8$ | $M=300000$ | ||
| $9$ | $N=15000$ | ||
| $10$ | $N=10000$ |
对于 5, 6 号测试点，保证按照如下方式随机生成:
- 均匀随机一条不在图中的非自环的边 $(u, v)$。
- 如果加入 $(u, v)$ 后，无论之后再怎么加边，都无法使得最终的图是个连通图，那么就不加入这条边；否则加入这条边。
- 重复操作直至加入恰好$M$条边为止。
对于其他测试数据，保证按照如下方式随机生成：
- 均匀随机一条不在图中的非自环的边 $(u, v)$。
- 重复操作直至加入恰好$M$条边为止。
时间限制：$4\texttt{s}$
空间限制：$512\texttt{MB}$
提示
你的程序可以通过判断传入的 $N$ 的个位来区分上述不同的数据类型。
鄂公网安备 42010202000505 号