Graph Coloring

You are given a graph, and you must color each node either black or white. The only available colors are black and white. No two nodes joined by an edge may both be black. Subject to this rule, a coloring is called optimal when the number of black nodes is as large as possible.

For each graph, find the maximum number of nodes that can be colored black, together with one optimal coloring that achieves it. Equivalently, the black nodes form an independent set (no two of them are adjacent), and you want such a set of maximum size.

The nodes of a graph are numbered $1$ through $n$, with $n \le 100$. Each edge is undirected and is given as a pair of distinct node numbers $(n_1, n_2)$ with $n_1 \ne n_2$.

The first line contains the number of graphs $m$. Each graph is then described as follows: its first line contains $n$ and $k$, the number of nodes and the number of edges, separated by a space; the next $k$ lines each contain the two node numbers of one edge, separated by a space.

For each graph, print two lines, for a total of $2m$ lines. The first line contains the maximum number of nodes that can be colored black. The second line contains the optimal coloring: list the black nodes in increasing order, separated by single spaces.

Because several optimal colorings may exist, print the one that is lexicographically smallest. That is, among all optimal colorings, compare the sorted (increasing) lists of black-node numbers element by element, and print the smallest such list.