POLSKI SPOJ

Jaś znalazł ostatnio w internetach bardzo fajną, lecz czasem trudną do przejścia grę. W grze masz daną planszę zawierającą n pól. Niektóre pola są połączone mostami umożliwiającymi przemieszczanie się. Celem w grze jest postawienie swojej postaci na jednym z pól, a następnie odwiedzenie jak największej ilości wierzchołków przemieszczając się przy użyciu mostów. Jednak gdyby to było wszystko, to gra byłaby za łatwa i za nudna. Haczykiem jest to, że jeśli zejdziemy z jakiegoś pola, to pole to się zapada. Jaś świetnie sobie do tej pory radził, lecz liczba pól i mostów zaczęła szybko rosnąć, i przy n równym 10⁴ Jaś wymiękł. Pomóż mu więc!

Input

Liczba zestawów danych t.

Każdy zestaw danych wygląda następująco.

Dwie liczby n i m (1 ≤ n, m ≤ 10⁵) oznaczające liczbę pól oraz liczbę mostów.

W każdej z następnych m linii znajdują się dwie liczby a i b oznaczające że istnieje dwukierunkowy most umożliwiający przejście z pola a do b lub na odwrót.

Suma wszystkich n i m w jednym teście nie przekroczy 10⁶.

Output

Dla każdego testu należy wypisać w pierwszym wierszu liczbę x oznaczającą ilość pól na znalezionej drodze.

W drugim wierszu każdego testu powinien znaleźć się ciąg różnych liczb oznaczający kolejno odwiedzane wierzchołki.

Zestawy danych oddzielone są pustą linią.

Punktacja

We wszystkich sześciu testach znajduje się dokładnie 266 grafów. Za każdy graf dostaje się tyle punktów ile jest pól na znalezionej drodze. Ilość pól na znalezionej drodze zawsze musi być większa niż 0.

Testy wyglądają tak:

• 1 i 2 test: (1 ≤ n ≤ 100, 1 ≤ m ≤ 1000). Limit: 10s.
• 3 test: (1 ≤ n ≤ 1000, 1 ≤ m ≤ 100000). Limit: 10s.
• 4 test: (1 ≤ n ≤ 10000, 1 ≤ m ≤ 100000). Limit: 10s.
• 5 i 6 test: (1 ≤n ≤ 100000, 1 ≤ m ≤ 100000). Limit: 10s.

We wszystkich testach istnieje ścieżka umożliwiająca przejście całego grafu.

Maksymalnie do zdobycia jest aż 402217 punktów.

Example

Input:

Output: