Multidrink
Limit pamięci: 256 MB
Bajtazar mieszka w Bajtowie, które słynie z tego, że przy każdym skrzyżowaniu
ulic znajduje się bar mleczny.
Pewnego dnia Bajtazar postanowił odwiedzić w celu tzw. "mlecznego multidrinka"
wszystkie bary, każdy dokładnie raz.
Bajtazar chciałby tak zaplanować trasę, żeby każdy kolejny bar był
nie dalej niż dwa skrzyżowania od poprzedniego.
Skrzyżowania w Bajtowie są ponumerowane od do .
Wszystkie ulice są dwukierunkowe.
Między każdymi dwoma różnymi skrzyżowaniami jest tylko jedna trasa, na której
żadne skrzyżowanie nie powtarza się.
Bajtazar startuje przy skrzyżowaniu numer i kończy przy skrzyżowaniu numer .
Twoim zadaniem jest wyznaczenie jakiejkolwiek
trasy spełniającej wymagania Bajtazara lub wypisanie informacji o braku takiej trasy.
Trasą spełniającą warunki zadania jest na przykład:
Nie ma żadnej trasy spełniającej warunki zadania.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita
() oznaczająca liczbę skrzyżowań w Bajtowie.
Każdy z kolejnych wierszy zawiera dwie różne liczby całkowite oraz
(), oddzielone pojedynczym odstępem, reprezentujące ulicę
łączącą skrzyżowania o numerach i .
W testach wartych łącznie 65% punktów zachodzi dodatkowy warunek .
Wyjście
Jeśli nie istnieje żadna trasa spełniająca wymagania Bajtazara, w pierwszym
i jedynym wierszu standardowego wyjścia Twój program powinien wypisać jedno słowo "BRAK"
(bez cudzysłowów).
W przeciwnym przypadku Twój program powinien wypisać wierszy, z których -ty
powinien zawierać numer -tego skrzyżowania na przykładowej trasie spełniającej warunki Bajtazara.
W pierwszym wierszu powinna znaleźć się liczba 1, a w -tym wierszu - liczba .
Przykład
Dla danych wejściowych:
12
1 7
7 8
7 11
7 2
2 4
4 10
2 5
5 9
2 6
3 6
3 12
poprawną odpowiedzią jest:
1
11
8
7
4
10
2
9
5
6
3
12
natomiast dla danych wejściowych:
15
1 14
14 7
7 8
7 11
7 2
2 4
4 10
2 5
5 9
2 6
3 6
3 15
11 12
8 13
poprawnym wynikiem jest:
BRAK
Autorzy zadania: Jakub Radoszewski, Wojciech Rytter.