描述

你需要编写一个程序，尝试为给定的图找到一种最优着色方案。着色方案将颜色应用于图的节点，可用的颜色只有黑色和白色。如果图中黑色节点的数量最多，则该着色方案称为最优。着色方案受到以下规则的限制：任何两个相连的节点不能同时为黑色。

图1：一个包含三个黑色节点的最优图

输入

图由一组编号为$1...n$的节点表示，其中$n \leq 100$，以及一组由节点对$(n1, n2)$（$n1 \neq n2$）表示的无向边。输入文件包含$m$个图。第一行给出$m$的值。每个图的第一行包含$n$和$k$，分别表示节点数和边数。接下来的$k$行包含由空格分隔的节点对表示的边。

输出

输出应包含$2m$行，每个图对应两行。第一行应包含图中可以着黑色的最大节点数。第二行应包含一种可能的最优着色方案，由空格分隔的黑色节点列表表示。

输入数据 1

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

输出数据 1

3  
1 4 5

来源

1995年西南欧区域竞赛