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

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

zerojudge無法進行特殊判斷，輸出的答案若有多組解，輸出字典順序最小的一組解。 

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

3
1 4 5
2
1 2
3
1 5 6