Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NPNPNPNP - Dziwna gra

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 104 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 ≤ 105) 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 106.

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:
2

4 4
1 2
1 3
2 3
2 4

2 1
1 2

Output:

4
1 3 2 4
2
1 2

Dodane przez:Bartek
Data dodania:2015-02-07
Limit czasu wykonania programu:10s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.