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.|

CHAL0001 - Wysadzanie grafu

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

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 ni wierzchołków, a znalezione poprawne rozwiązanie wymaga podłożenia bomby pod xi wierzchołków to ilość punktów zdobyta za ten graf wynosi xi / ni * 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.

 


Dodane przez:Bartek
Data dodania:2015-02-05
Limit czasu wykonania programu:5s
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.