Historia OI -> XIII OI 2005/2006

SIO

MAIN

Zadanie: Profesor Szu

Dostępna pamięc: 32MB

W mieście Bajtion ma swoją siedzibę bajtocki uniwersytet. Oprócz głównego gmachu, uniwersytet ma do dyspozycji n domków dla pracowników naukowych. Domki połączone są jednokierunkowymi drogami, może jednak być wiele dróg łączących dwa domki, istnieją także drogi łączące gmach uniwersytetu z domkami (droga może łączyć także pewien obiekt z nim samym). Bajtion został tak skonstruowany, żeby żadne drogi się nie przecinały w miejscach innych niż domki lub gmach (ale mogą przebiegać mostami i tunelami) ; ponadto każda droga zaczyna się w pewnym domku lub w gmachu i kończy się w domku lub w gmachu. Wiadomo ponadto, że istnieje co najmniej jedna droga łącząca pewien domek z gmachem uniwersytetu.

Pewnego razu uniwersytet zapragnął zatrudnić u siebie znanego specjalistę informatyki teoretycznej - profesora Szu. Jak wielu wielkich naukowców, profesor Szu ma dziwny zwyczaj; otóż każdego dnia lubi dojeżdżać do gmachu uniwersytetu inną trasą (będącą drogą bądź układem dróg, z których każda następna zaczyna się w domku, w którym kończy się poprzednia; trasa może przechodzić przez ten sam domek bądź główny gmach uniwersytetu wielokrotnie). Profesor dwie trasy uważa za różne, jeżeli różnią się chociaż jedną wykorzystaną drogą (przy czym kolejność dróg jest ważna, a dwie różne drogi łączące te same domki uważa on za różne).

Znając schemat połączeń między domkami Bajtionu, pomóż uniwersytetowi znaleźć domek, z którego istnieje najwięcej różnych tras do gmachu uniwersytetu (zamieszkawszy w tym domku, profesor Szu będzie chciał najdłużej pracować na uczelni) - jeżeli takich domków jest więcej niż jeden, to podaj wszystkie z nich. Jeżeli przy tym z jakiegoś domku istnieje więcej niż 36 500 tras do gmachu, to zakładamy, że profesor może tam zamieszkać na zawsze (jako że nie może żyć nieskończenie długo, a 100 lat to dość bezpieczna granica).

Zadanie

Napisz program, który:

wczyta ze standardowego wejścia schemat połączeń między domkami Bajtionu,
wyznaczy domki, w których profesor Szu mógłby mieszkać najdłużej oraz najdłuższy czas jego zamieszkiwania,
wypisze wynik na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite n oraz m ( 1 $$ \le$% WIDTH=16 HEIGHT=30$ n, m $$ \le$% WIDTH=16 HEIGHT=30$ 1 000 000) oddzielone pojedynczym odstępem i oznaczające odpowiednio ilość domków i ilość dróg w Bajtionie (domki są ponumerowane liczbami od 1 do n, a umownie nadajemy gmachowi uniwersytetu numer n + 1). W wierszach o numerach od 2 do m + 1 znajdują się pary liczb całkowitych a_i, b_i ( 1 $$ \le$% WIDTH=16 HEIGHT=30$ a_i, b_i $$ \le$% WIDTH=16 HEIGHT=30$ n + 1 dla 1 $$ \le$% WIDTH=16 HEIGHT=30$ i $$ \le$% WIDTH=16 HEIGHT=30$ m) oddzielone pojedynczymi odstępami i oznaczające odpowiednio numer domku w którym zaczyna się i numer domku w którym kończy się i-ta droga.

Wyjście

Pierwszy wiersz wyjścia powinien zawierać maksymalną liczbę dni jaką profesor Szu może mieszkać w Bajtionie lub jedno słowo ,,zawsze'', jeżeli ta liczba przekracza 36 500 dni. W drugim wierszu powinna się znajdować liczba domków, zamieszkanie w których zapewnia profesorowi okres pobytu podany w pierwszym wierszu wyjścia. W trzecim wierszu powinny się znaleźć numery wszystkich takich domków, oddzielone pojedynczymi odstępami i podane w kolejności rosnącej. Wszystkie domki, w których profesor może zamieszkać na zawsze uważamy przy tym za jednakowo dobre.

Przykład

Dla danych wejściowych:

poprawną odpowiedzią jest:

4
1
1

Natomiast dla danych:

poprawną odpowiedzią jest:

zawsze
3
1 2 3

Wersja do druku