Stowarzyszenie UCPC ogłosiło trzy lata temu, że zmieni format zawodów na turniejowy, jednak ze względu na zbyt duże zmiany napotkało wiele trudności. Hye-ah, która w tym roku objęła stanowisko przewodniczącej stowarzyszenia, przeglądając dokumenty wewnętrzne, natrafiła na zapisy z przygotowań do tamtych zawodów i postanowiła ponownie zorganizować turniej.

Na szczęście w tegorocznych zawodach UCPC wzięło udział dokładnie $2^N$ uczestników, dzięki czemu Hye-ah mogła przeprowadzić zawody w bardzo przejrzysty sposób, stosując system pucharowy (single-elimination). Jest to format zawodów, który zazwyczaj przychodzi na myśl jako pierwszy, gdy słyszymy słowo „turniej”. Proces ten przebiega następująco:

1. Uczestnikom przypisuje się unikalne numery rozstawienia od $1$ do $2^N$ i ustawia ich w rzędzie w dowolnej kolejności.
2. Uczestników w rzędzie łączy się w pary, biorąc ich kolejno od początku. Każda para rozgrywa mecz jeden na jednego, a przegrany odpada z turnieju. Po rozegraniu wszystkich meczów w danej rundzie liczba uczestników pozostających w rzędzie zmniejsza się o połowę.
3. Powtarzając proces z punktu 2 dokładnie $N$ razy, pozostaje tylko jeden uczestnik, który zostaje zwycięzcą turnieju.

Turniej pucharowy jest często przedstawiany w formie drabinki turniejowej w kształcie drzewa binarnego, jak pokazano poniżej.

Rysunek K.1: Przykład drabinki turniejowej dla $2^3 = 8$ uczestników

Komitet organizacyjny, w tym Hye-ah, nadzorował wszystkie mecze i zapisywał wyniki w udostępnionym dokumencie. Jednak z powodu chaotycznego wpisywania wyników przez wiele osób, dokument stał się całkowicie nieczytelny. Co więcej, po zakończeniu zawodów organizatorzy policzyli liczbę meczów i z przerażeniem odkryli, że brakuje jednego wyniku.

W zastępstwie organizatorów, którzy są zbyt wyczerpani przebiegiem zawodów, aby samodzielnie naprawić tę sytuację, znajdź brakujący wynik meczu.

Wejście

W pierwszej linii podana jest liczba całkowita $N$ ($2 \le N \le 20$).

W kolejnych $2^N - 2$ liniach podane są dwie liczby całkowite $a_i$ oraz $b_i$ oddzielone spacją, reprezentujące wynik każdego meczu. Oznacza to, że w meczu zmierzyli się uczestnik o numerze $a_i$ oraz uczestnik o numerze $b_i$, a zwycięzcą został uczestnik $a_i$.

Gwarantuje się, że dane wejściowe zawierają pełny zapis przebiegu zawodów z jednym brakującym meczem. Oznacza to, że nie zostaną podane dane, dla których nie da się stworzyć poprawnego przebiegu zawodów przy żadnym założeniu dotyczącym brakującego meczu.

Wyjście

Wypisz wynik brakującego meczu w tym samym formacie co dane wejściowe, podając dwie liczby całkowite. Jeśli istnieje wiele możliwych wyników meczu, wypisz wszystkie poprawne odpowiedzi, każdą w osobnej linii. Odpowiedzi należy posortować najpierw według numeru zwycięzcy (rosnąco), a w przypadku takich samych numerów zwycięzców – według numeru przegranego (rosnąco).

Przykład

Wejście 1

3
3 6
1 8
3 7
3 5
6 1
7 4

Wyjście 1

6 2

Wejście 2

2
3 4
1 2

Wyjście 2

1 3
3 1

Uwagi

Drabinka turniejowa w pierwszym przykładzie odpowiada rysunkowi przedstawionemu w treści zadania.

W drugim przykładzie, w zawodach z $2^2 = 4$ uczestnikami, brakuje zapisu finału. Ponieważ nie wiadomo, kto wygrał finał, należy wypisać obie możliwości.