Graph Coloring

Interview

Time limit1sMemory limit128 MB

Summary

For each graph, find a maximum independent set and output one optimal coloring whose sorted black node list is lexicographically smallest.

Level: Medium7 of 10
Topics: Graph, Backtracking, Greedy, Brute force
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples3

Example 1

Input

Expected output

3
1 4 5

Example 2
Input
```
1
5 0
```
Expected output
```
5
1 2 3 4 5
```
Example 3
Input
```
1
5 4
1 2
2 3
3 4
4 5
```
Expected output
```
3
1 3 5
```