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).
Dla danych wejściowych:3 5 1 2 1 3 2 3 3 4 3 4poprawną odpowiedzią jest: 4 1 1 |
|
3 5 1 2 2 3 3 1 3 4 3 4poprawną odpowiedzią jest:
zawsze 3 1 2 3