POLSKI SPOJ

Jaś otrzymał ostatnio na urodziny graf. Chciałby teraz ten graf wysadzić zużywając przy tym jak najmniej bomb. Wysadzanie odbywa się w następujący sposób. Jaś kładzie bomby na niektórych wierzchołkach (możliwe, że wszystkich), a następnie wszystkie bomby wybuchają jednocześnie i zabierają ze sobą w zaświaty wierzchołek na którym stały oraz wszystkie wierzchołki sąsiednie (czyli bezpośrednio połączone krawędzią).

Jak już było napisane, Jaś chciałby zużyć jak najmniejszą ilość bomb, więc poprosił Cię o pomoc w tym zadaniu.

Wejście

W pierwszej linii wejścia znajduje się liczba zestawów danych t (1 ≤ t ≤ 100). Każdy z następnych zestawów wygląda następująco.

W pierwszej linii dwie liczby n i m (1 ≤ n, m ≤ 2 * 10⁵) oznaczające kolejno ilość wierzchołków w grafie oraz ilość krawędzi. Może istnieć wiele krawędzi między parą wierzchołków, oraz krawędzie zaczynające się i kończące na tym samym wierzchołku. Graf nie musi być spójny.

W każdej z kolejnych m linii znajdują się dwie liczby a i b (1 ≤ a, b ≤ n) oznaczające, że istnieje krawędź łącząc wierzchołek a z wierzchołkiem b.

Suma wszystkich n i m w zestawach danych w jednym teście nie przekracza 10⁶.

Zestawy danych oddzielone są pojedynczą pustą linią. Po liczbie zestawów danych nie ma pustej linii!

Wyjście

Dla każdego zestawu danych, wyjście ma wyglądać następująco:

W pierwszej linii wyjścia musi znajdować się liczba x oznaczająca ilość bomb do podłożenia.

W drugiej linii ma znajdować się x liczb oznaczających numery wierzchołków, pod które należy podłożyć bomby. Kolejność tych liczb nie ma znaczenia.

Punktacja

Rozwiązanie nie musi być idealne, to znaczy ilość bomb nie musi być minimalna, lecz bomby muszą zawsze być ułożone w taki sposób, że graf zostanie w pełni wysadzony. Jeśli w przynajmniej jednym teście graf nie zostanie w pełni wysadzony, rozwiązanie zwróci niepoprawną odpowiedź.

Istnieje 1000 grafów do sprawdzenia. Jeśli w i'ty graf posiada n_i wierzchołków, a znalezione poprawne rozwiązanie wymaga podłożenia bomby pod x_i wierzchołków to ilość punktów zdobyta za ten graf wynosi x_i / n_i * 100.

Im mniej punktów otrzyma rozwiązanie tym lepiej!

Przykład 1

Wejście:

2
3 2
1 2
2 3

3 2
1 2
2 3

Wyjście:

2
1 3
1
2

Ilość punktów za test:

66 punktów za pierwszy graf oraz 33 punkty za drugi graf. Razem 99 punktów.