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.