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

BSPIES - Ustawione sojusze

W ostatnich latach rywalizacja pomiędzy miastami Bajtlandii, tradycyjnie przejawiająca się w konkursach ogrodniczych, przybrała bardziej militarny charakter. Wybuch wojny domowej wydaje się wręcz nieuchronny. Trochę kłopotliwe jest jednak często stawiane pytanie, kto będzie walczył przeciwko komu; wydaje się, że nawet burmistrzowie zainteresowanych miast nie do końca znają na nie odpowiedź. Aby uporządkować sytuację, w stolicy zwołano Walny Zjazd Emisariuszy Miast Bajtlandii (WZEMB). Jego głównym celem jest powołanie do życia frakcji, które będą walczyły przeciwko sobie.

Zasada obrad WZEMBu jest prosta. Jeden po drugim, emisariusze podchodzą do Karty z wypisaną na niej listą frakcji. Karta początkowo jest pusta. Każdy emisariusz, czytając Kartę od góry do dołu, stara się znaleźć na niej pierwszą frakcję, w skład której wchodzą wyłącznie miasta nie będące w stanie konfliktu z miastem reprezentowanym przez emisariusza. Jeżeli taka frakcja istnieje, emisariusz dołącza do niej nazwę swojego miasta; jeżeli nie -- zakłada dla swojego miasta nową frakcję, dodając wpis nowej frakcji pod wszystkimi innymi.

Sprawami wewnętrznymi Bajtlandii są żywotnie zainteresowani jej, nie zawsze życzliwie nastawieni, sąsiedzi. Agentom bitlandzkiego wywiadu udało się uzyskać dostęp do tajnych planów bajtlandzkiego WZEMBu. Mają teraz możliwość wpłynięcia na jego program poprzez zmodyfikowanie kolejności, w której emisariusze podchodzą do Karty. Zamierzonym celem jest doprowadzenie do sytuacji, w której liczba powstających w Bajtlandii frakcji jest możliwie jak największa. Spróbuj napisać program automatyzujący to zadanie.

Wejście

W pierwszej linii pliku wejściowego podano liczbę przypadków testowych t (t=100). Każdy przypadek testowy zaczyna się od linii zawierającej liczbę całkowitą n, oznaczającą liczbę miast w Bajtlandii (1<=n<=5000). W kolejnej linii podana jest liczba całkowita m (1<=m<=10000). Każda z kolejnych m linii zawiera parę liczb całkowitych a b oddzielonych spacją, oznaczającą, że miasta a i b znajdują się w stanie konfliktu ze sobą (1<=a,b<=n).

Wyjście

Dla każdego przypadku testowego wypisz ciąg n liczb identyfikujących miasta, których emisariusze powinni kolejno podchodzić do Karty.

Wynik

Wynik uzyskany przez program jest równy całkowitej liczbie frakcji, które powstaną w Bajtlandii (zsumowanej po wszystkich przypadkach testowych).

Przykład

Wejście:
2

3
2
1 2
3 2

4
3
2 3
4 3
1 2

Wyjście:
1 2 3
1 4 3 2

Wynik:
2pkt. + 3pkt. = 5pkt.

Dodane przez:adrian
Data dodania:2006-05-28
Limit czasu wykonania programu:4s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.