Graph Coloring

# 题目描述 请您编写一个程序找到一个给定图的最优染色方案。染色是指对图上的点染色，并且只有黑白二色可用。最优染色方案要求染成黑色的点最多。染色限制：禁止由一条边相连的两个点都染黑色。 # 输入格式 给定的图由点和无向边构成。点用1...n, n<=100来表示。无向边用两个顶点来表示，这两个顶点不会相同。 输入数据有m个图。第1行给出m。每个图的第一行给出两个数字n和k，分别指点数和边数。接下来的k行包含k条边的两个顶点，两个数字之间以空格相间。 # 输出格式 输出包含2m行，输入的每个图对应2行。每个图的第1行输出最大染黑点数，第2行输出一种可能的最优染色方案，即输出所有染黑的点，每两个点间以空格相间。

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=129 [PDF](https://uva.onlinejudge.org/external/1/p193.pdf) 



1
6 8
1 2
1 3
2 4
2 5
3 4
3 6
4 6
5 6

3
1 4 5