This is an interactive problem.

Xiao Z has an undirected graph with $n$ vertices and $m$ edges, containing no self-loops. Xiao U wants to know the structure of this graph, but Xiao Z refuses to tell him.

Xiao Z: "I can tell you that the graph is connected, the vertices are labeled from $0$ to $n-1$, and the edges are labeled from $0$ to $m-1$."

Xiao U: "Well, what is the connectivity of the graph after removing an edge?"

Xiao Z: "You won't be able to guess it anyway, so let's do this: each time, you provide me with a set of edge indices $S$ and a vertex $u$, and I will calculate whether vertex $0$ and vertex $u$ are connected using only the edges with indices in $S$."

After hearing this, Xiao U pondered for a long time but still could not figure out how to determine the two endpoints of every edge in the graph.

Therefore, he has come to you for help to find out the information about the graph. We guarantee that the graph is pre-generated, meaning it will not change based on Xiao U's queries. You cannot make too many queries; you must obtain the information about the graph within $30,000$ queries!

Implementation Details

You do not need to implement the main function; you only need to implement the following function:

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

This function should return an array $e$ of length $m$, where $e[i]$ represents the two endpoints connected by the $i$-th edge (the order of the pair does not matter).

Additionally, you must include the graph.h header file in your submitted file. We have provided sample_graph.cpp for your reference.

The function you implement can call the function provided by the interactive library:

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

In this function, $u$ is an integer in $[0, n-1]$, and $s$ is an int array of length $m$, where values can only be $0$ or $1$. If $s[i] = 1$, it means the $i$-th edge is included in the set $S$ queried by Xiao U; otherwise, it is not. The meaning of this function is to query whether vertex $0$ can reach vertex $u$ using only the edges with indices in $S$.

Testing Procedure

You can use the following compilation command:

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

For the resulting grader, the input data is provided as follows:

The first line contains two positive integers $n, m$.

The next $m$ lines each contain two integers $u_i, v_i$, representing an edge in the graph.

If your answer is correct, the grader will output Accepted!You made x attempt(s)., where $x$ is the number of times you called the query function.

Otherwise, you will receive some error information. You can compare your code with the grader.cpp code and the error messages it outputs to determine the cause of your error. However, the grader will not verify whether your input is correct!

Subtasks

For $100\%$ of the data, it is guaranteed that $1 \le n, m \le 600$.