题目描述

这是一道交互题。

注意：本题只支持以下语言的提交：

• C++
• C++ 11
• C++ 17
• C++ (NOI)
• C++ 11 (NOI)
• C++ 11 (Clang)
• C++ 17 (Clang)

小 Z 有一张 $n$ 个点 $m$ 条边的没有自环的无向图。小 U 想要知道这张图的样子，但小 Z 不肯告诉它。

小 Z：我可以告诉你这张图是连通的，点从 $0$ 标号至 $n-1$，边从 $0$ 标号至 $m-1$。

小 U：好那删掉一条边后，这张图的连通状况如何呢？

小 Z：反正你也猜不出来，就这样吧。你每次告诉我一个边的编号的集合 $S$，再给定一个点 $u$，然后我可以帮你计算把编号在 $S$ 中的边连接后，$0$ 号点与点 $u$ 是否连通。

听到小 Z 的这句话后，小 U 苦思冥想，仍然不知道如何才能问出这张图的每条边到底连接哪两个端点。

因此他找到了你，想让你帮他问出这张图的信息。我们保证这张图是预先生成的，也就是说不会随小 U 的询问而改变。并且你不能询问太多次，你需要在 $\mathbf{30000}$ 次内得到这张图的信息！

实现细节

你不需要实现主函数，你只需实现一个函数：

std::vector<std::pair<int, int> > solve(int n, int m)

这个函数应该返回一个长度为 $m$ 的数组 $e$，其中 $e[i]$ 表示第 $i$ 条边连接的两个端点（顺序无关）。

同时，你需要在你提交的文件中包含 graph.h 头文件，我们下发了 sample_graph.cpp 供你做参考。

你所实现的函数可以调用交互库中的函数：

bool query(int u, std::vector<int> s)

这个函数中 $u$ 是一个 $[0, n-1]$ 中的整数，$s$ 是一个长度为 $m$ 的 int 数组，且值只能为 $0$ 或 $1$。若 $s[i] = 1$，则表示 $i$ 是否在小 U 询问的集合 $S$ 中，否则不在集合 $S$ 中。这个函数的意义是给定 $u$ 和 $S$，询问 $0$ 号点能否通过编号在 $S$ 中的边到达 $u$。

测试程序方式

你可以调用编译命令：

g++ graph.cpp grader.cpp -o grader -O2 -std=c++11

对于得到的 grader，会按如下方式输入数据：

第一行输入两个正整数 $n,m$。

接下来 $m$ 行，每行输入两个整数 $u_i, v_i$，表示图中的一条边。

如果你的答案正确，grader 会输出 Accepted!You made x attempt(s).，其中 $x$ 是你调用的 query 函数的次数。

否则你会得到一些错误信息。你可以对照着 grader.cpp 的代码和它输出的错误信息来判断你的错误原因。但 grader 不会检验你的输入是否正确！

数据范围与提示

对于 $100\%$ 的数据，保证 $1\le n, m\le 600$。