Q193: Graph Coloring

給你一個圖形，你的任務是找到一種最佳塗色的方法。圖形中的點要被塗顏色（只能塗黑色或白色），而且任何2個相連的點不可以都塗黑色。所謂最佳的塗色方法是指讓這個圖形黑色的點最多。以下圖形的塗色即是一種最佳塗色：

Input

輸入的第一列有一個整數，代表以下有多少組測試資料。

每組測試資料的第一列含有2個整數 n ( 1 <= n <= 100 )，k。n 代表圖形中點的數目（編號從1到 n），k 代表圖形中邊的數目。接下來的 k 列每列含有 2 個點的編號，代表一個邊。請參考Sample Input。

Output

對每一組測試資料輸出 2 列。第一列輸出最多可以有多少個點可以被塗黑色。第二列輸出一種可能的塗法，以塗黑色點的編號來表示。請參考 Sample Output。

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

3
1 4 5
2
1 2
3
1 5 6