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

MWP3_1E1 - PIT

Jan po ukończeniu studiów bez problemu znalazł pracę jako programista w firmie Trouble Inc. Miesiące mijały naszemu bohaterowi na beztroskim programowaniu i startach w zawodach algorytmicznych, aż nadszedł ten straszny dzień - dzień złożenia PITu! Zapewne wszyscy mieli/będą mieli1 niewątpliwą/wątpliwą2 przyjemność wypełniania i składania różnego rodzaju formularzy w urzędzie skarbowym. Procedury tam obowiązujące, co powszechnie wiadomo, są szalenie skomplikowane, a załatwienie czegokolwiek niezwykle trudne, czasami wręcz niemożliwe. Jan chcąc złożyć formularz A dowiedział się, że najpierw musi wypełnić i złożyć formularz B. Niestety, formularza B nie można złożyć bez wcześniejszego uzupełnienia formularza C itd... Jan postanowił załatwić sprawę jak na informatyka przystało - napisać program, który ustali kolejność składania formularzy. Spisał on pary formularzy jakie należy wypełnić i złożyć, uwzględniając przy tym ich kolejność. Zapis 1 2 oznaczał, że formularz 1 należy złożyć przed formularzem 2. Po spisaniu wszystkich par okazało się, że kolejności wypełniania niektórych formularzy nie da się ustalić np. dla par: 1 2, 2 3, 3 1. W takim wypadku nasz bohater grupował formularze i oznaczał grupę największym spośród numerów formularzy. W podanym przypadku byłby to numer 3. Jan napisał program i złożył swój PIT przed upływem terminu. Nie zapominaj jednak, że i Ty trafisz kiedyś do urzędu skarbowego z podobnym problemem - nie zwlekaj napisz swój program już dziś!

Wejście

W pierwszej linii wejścia znajduje się jedna liczba naturalna Z (1 ≤ Z ≤ 5) określająca ilość zestawów danych. W kolejnych liniach znajdują się zestawy danych.

W pierwszej linii każdego zestawu danych znajdują się dwie liczby naturalne n oraz m (2 ≤ n ≤ 1000; (n - 1) ≤ m ≤ ((n - 1) × n) ) określające odpowiednio ilość formularzy do wypełnienia oraz ilość zapisanych par określających kolejność. W kolejnych m liniach znajdują się po dwie liczby naturalne a i b (0 ≤ a, b < n i ab) określające, że formularz o numerze a powinien zostać złożony przed formularzem o numerze b. Gwarantujemy, że każdy formularz wystąpi w przynajmniej jednej parze.

Wyjście

Dla każdego zestawu należy wypisać numery formularzy oraz ewentualnych grup formularzy w kolejności składania. W przypadku gdy istnieje kilka poprawnych ustawień należy wypisać to, które jest najmniejsze leksykograficznie.

Przykład

Wejście:

1
7 9
6 1
0 2
2 4
4 0
0 1
4 5
5 3
3 1
1 5

Wyjście:

4 6 5

1, 2 - niepotrzebne skreślić


Dodane przez:Maciej Boniecki
Data dodania:2010-12-02
Limit czasu wykonania programu:0.100s-1s
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
Pochodzenie:III Mistrzostwa WWSI w Programowaniu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.