XI Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 26 V 2007

Opis

Za górami, za lasami, za głębokimi jeziorami, na bardzo wysokich skałach, w bardzo starym zamczysku żyły sobie bardzo nowoczesne duchy. Każdy z nich miał swoją prywatną komnatę, w której ćwiczył sztukę perfekcyjnego straszenia zabłąkanych turystów. Duchy lubiły swoje własne towarzystwo, więc po długich godzinach ćwiczeń bardzo często odwiedzały się wzajemnie, żeby sobie poplotkować. Ponieważ jednak przechodzenie przez bardzo grube mury w solidnie zbudowanym zamku było bardzo męczące (a duchy miały już swoje lata), więc postanowiły sobie zamówić urządzenia do teleportacji. Z powodu jednak zbyt małej liczby gotówki zostawianej przez nielicznie odwiedzających zamczysko ludzi, nie starczyło im jej na zakup "tuneli teleportacyjnych" z każdej komnaty do wszystkich pozostałych. Dlatego trzeba było wybrać, które komnaty połączyć jednokierunkowym tunelem z innymi. Stało się to przyczyną wielkiej kłótni, ponieważ każdy duch miał swoje własne ulubione ścieżki pomiędzy komnatami. W końcu postanowiono, że będą losowały dwa numery komnat a i b, a następnie połączą komnatę a-tą z b-tą jednokierunkowym tunelem (którym można się teleportować z komnaty a do b). Całą operację powtarzały dopóki miały pieniądze na zakup kolejnego tunelu. Wszystko byłoby dobrze, ale po pilotażowym zainstalowaniu okazało się, ze teleportacja tak się duchom spodobała, że zamiast ćwiczyć trudną sztukę straszenia ludzi, ciągle teleportowały się w kółko z jednej komnaty do drugiej. Aby temu zapobiec postanowiono, że nie będą instalowały tuneli, które umożliwiałyby niekończące się teleportacje - konieczność "zwykłego" przechodzenia przez ściany była wystarczająco męcząca i powodowała, że duchy nie teleportowały się bez celu.

Twoim zadaniem, jako pracownika dystrybutora "tuneli teleportacyjnych" jest wskazanie, których tuneli z listy podanej przez duchy nie należy instalować.

Specyfikacja wejścia

W pierwszej linii znajduje się liczba komnat w zamku (1 ≤ K ≤ 1000). W drugiej linii znajduje się liczba wylosowanych przez duchy tuneli (1 ≤ T ≤ 300000). W następnych T liniach znajdują się kolejno wylosowane liczby a oraz b (1 ≤ a,b ≤ K).

Specyfikacja wyjścia

W kolejnych liniach należy podać opis tuneli których nie należy instalować. Muszą być one wypisane w takiej samej kolejności w jakiej znajdowały się na liście dostarczonej przez duchy. Wyjście należy zakończyć linią zawierającą dwa zera odzielone spacją.

Przykład

4
5
2 4
4 3
3 2
1 2
3 1

3 2
3 1
0 0