Inspekcja
Limit pamięci: 128 MB
Sieć kolejowa Bajtockich Kolei Bitowych (BKB) składa się z dwukierunkowych odcinków torów łączących pewne pary stacji.
Każda para stacji jest połączona co najwyżej jednym odcinkiem torów.
Ponadto wiadomo, że z każdej stacji kolejowej można dojechać do każdej innej dokładnie jedną trasą.
(Trasa może być złożona z kilku odcinków torów, ale nigdy nie przechodzi przez żadną stację więcej niż raz).
Bajtazar jest tajnym inspektorem BKB.
W celu przeprowadzenia inspekcji wybiera jedną ze stacji (oznaczmy ją ), w której organizuje sobie centralę,
i rozpoczyna podróż po wszystkich innych stacjach.
Podróż ma następujący przebieg:
-
Bajtazar zaczyna w stacji .
-
Następnie wybiera jedną ze stacji jeszcze nie skontrolowanych i przemieszcza się do niej po najkrótszej ścieżce,
dokonuje tam inspekcji i wraca do .
-
Nieuczciwi pracownicy BKB ostrzegają się nawzajem o przyjeździe Bajtazara.
Aby ich zmylić, następną stację do skontrolowania Bajtazar wybiera w taki sposób, aby wyjechać
w inną stronę ze stacji niż poprzednio, tzn. innym odcinkiem torów wychodzącym z .
-
Każda stacja (poza stacją ) jest kontrolowana dokładnie raz.
-
Po skontrolowaniu ostatniej stacji Bajtazar nie wraca do .
Przejazd każdym odcinkiem torów trwa tyle samo - jedną godzinę.
Bajtazar pragnie rozważyć wszystkie możliwe stacje jako stacje początkowe .
Dla każdej z nich chcemy wyznaczyć kolejność, w jakiej Bajtazar powinien kontrolować pozostałe stacje,
tak aby łącznie jak najmniej czasu spędził na przejazdach, o ile dla danej stacji w ogóle taka kolejność istnieje.
Wejście
Pierwszy wiersz standardowego wejścia zawiera jedną liczbę całkowitą (), oznaczającą liczbę stacji.
Stacje są ponumerowane od 1 do .
Kolejne wierszy opisuje odcinki torów, po jednym w wierszu.
W każdym z nich znajdują się dwie liczby całkowite (, ), oddzielone pojedynczym odstępem,
oznaczające, że istnieje odcinek torów łączący stacje i .
Każdy odcinek torów pojawia się w opisie dokładnie raz.
W testach wartych przynajmniej 30% punktów zachodzi dodatkowy warunek .
Wyjście
Twój program powinien wypisać na standardowe wyjście wierszy, a w każdym z nich po jednej liczbie całkowitej.
Liczba w -tym wierszu powinna być równa minimalnej liczbie godzin, jakie Bajtazar musi spędzić na przejazdach,
aby skontrolować stacje, dla - o ile dla szukana kolejność stacji istnieje.
W przeciwnym przypadku, w -tym wierszu powinna znaleźć się liczba .
Przykład
Dla danych wejściowych:
9
3 6
2 4
2 6
2 5
1 7
2 7
8 9
7 8
poprawną odpowiedzią jest:
-1
23
-1
-1
-1
-1
-1
-1
-1
Rysunek pokazuje przykładową sieć połączeń.
Szukana kolejność, w jakiej Bajtazar powinien kontrolować stacje, istnieje tylko dla .
Może to być na przykład: , , , , , , , .
Przy takiej kolejności kontrolowanych stacji Bajtazar spędzi na przejazdach łącznie godziny.
Autorzy zadania: Wojciech Rytter i Bartosz Szreder.