Given a simple undirected graph G with n vertices and m edges, your task is to select a sub-bipartite graph of G with at least m/2 edges.
In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are each independent sets. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.
Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.
In the mathematical field of graph theory, a subgraph is a graph G whose graph vertices and graph edges form subsets of the graph vertices and graph edges of a given graph G..
In graph theory, a simple graph is a graph containing no self-loops or multiple edges.
from wikipedia
The first line of the date is an integer T, which is the number of the text cases.
Then T cases follow, each case starts of two numbers N and M, representing the number of vertices and the number of edges, then M lines follow. Each line contains two integers x and y, means that there is an edge connected x and y. The number of nodes is from 1 to N.
1 <= T <= 100, 1 <= N <= 100, 0 <= M <= 10086
For each case, you should output two lines to describe your sub-graph, the first line is the set of U and the second line is the set of V.
Each line should output an integer F first, which is the total number of the vertices in this set, then F integers follow which are the number of each vertex of this part, see sample input and sample output for more details.
You can assume that the answer is always existed.
3 1 0 2 1 1 2 3 3 1 2 2 3 1 3
1 1 0 1 1 1 2 2 1 2 1 3