这是一道交互题。

出题人 02 喜欢网上冲浪。可是这天，他所在的小区的网络坏掉了，于是他喊来了你帮忙修一修。

小区的网络由 $N$ 个网络结点和 $M$ 条信道组成，可以被看作是一张 $N$ 个点 $M$ 条边的无向简单图（简单图满足任意两点之间至多存在一条直接相连的边，且没有自环）。点从 $1 \sim N$ 编号，边从 $1 \sim M$ 编号。目前，你只知道信道的总数是 $M$，并且还掌握着每条信道的管理权限，然而你并不知道每条信道连接着哪两个结点。

为了恢复出网络结构，你可以使用一种土办法：重启大法！

当然重启也是需要智慧的。具体来说，你可以进行若干次操作，每次操作方式如下：

1. 给每个结点 $i$ 标上一个自己定的权值 $a_i$；
2. 选取一个信道的子集 $S$，把不在 $S$ 里的信道都关闭，只让 $S$ 里的信道保持开启状态；
3. 此时，每个结点 $i$ 会自动计算出与 $i$ 通过开启状态的信道直接相邻的所有点 $v$ 的 $a_v$ 异或和，记为 $b_i$；
4. 你通过管理员权限获取所有结点的 $b_i$ 值，然后关闭的信道都重启，网络恢复至原状。

请你在不超过 $50$ 次操作内，求出所有信道构成的集合。

注意，你只需要求出信道的集合。即，你只需要恢复出哪些结点之间有信道，不用恢复出每条信道对应的编号。

实现细节

你不需要，也不应该实现主函数，你只需要实现函数 $\texttt{Solve(N, M)}$，这里的 $\texttt{N}$ 和 $\texttt{M}$ 分别表示结点和信道的个数。你可以通过调用如下函数来和交互库进行交互：

1. $\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。
2. $\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 是我们提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

1. 编译方法：
   • 你需要在本题目录下使用如下命令编译得到可执行程序：
     • g++ grader.cpp explore.cpp -o explore -O2 -lm
2. 对于编译得到的可执行程序：
   • 可执行文件将从标准输入读入以下格式的数据：
     • 第一行包含两个整数 $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 次。

下面是一个正确的交互过程：

样例一

见附加文件下载

样例二

见附加文件下载

评分方式

最终评测只会收取 explore.cpp，修改选手目录下其他文件对评测无效。

本题首先会受到和传统题相同的限制。例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制等会导致相应测试点得 $0$ 分等。你只能访问自己定义的和交互库给出的变量及其对应的内存空间，尝试访问其他空间将可能导致编译错误或运行错误。

在上述条件基础上，在一个测试点中，你得到满分，当且仅当：

1. 你的每次函数调用均合法，且调用 $\texttt{Query},\texttt{Report}$ 的次数分别不超过 $50$，$M$ 次。
2. 由于 $\texttt{Report}$ 的调用次数限制为 $M$，你的每次调用都必须记录一条新的且存在的边；即每次调用 $\texttt{report(x, y)}$ 时，应满足：有一条连接 $x$ 号点和 $y$ 号点的路径，且在这次调用之前从未调用过 $\texttt{report(x, y)}$ 或 $\texttt{report(y, x)}$。
3. 你实现的函数 $\texttt{Solve}$ 正常返回。
4. 在 $\texttt{Solve}$ 函数返回时，你已经通过调用 $\texttt{Report}$ 记录了全部 $M$ 条信道。

限制与约定

对于 5, 6 号测试点，保证按照如下方式随机生成:

• 均匀随机一条不在图中的非自环的边 $(u, v)$。
• 如果加入 $(u, v)$ 后，无论之后再怎么加边，都无法使得最终的图是个连通图，那么就不加入这条边；否则加入这条边。
• 重复操作直至加入恰好$M$条边为止。

对于其他测试数据，保证按照如下方式随机生成：

• 均匀随机一条不在图中的非自环的边 $(u, v)$。
• 重复操作直至加入恰好$M$条边为止。

时间限制：$4\texttt{s}$

空间限制：$512\texttt{MB}$

提示

你的程序可以通过判断传入的 $N$ 的个位来区分上述不同的数据类型。

下载

附加文件下载