Ассоциация студенческих клубов программирования (Jeondae-preyeon) три года назад объявила о переходе UCPC на турнирную систему, но столкнулась с множеством трудностей из-за слишком масштабных изменений. Хеа, ставшая в этом году председателем ассоциации, обнаружила в документах записи о подготовке того турнира и решила снова провести соревнование по турнирной системе.

К счастью, в этом году в UCPC участвует ровно $2^N$ человек, поэтому Хеа может провести турнир по системе с выбыванием (олимпийской системе). Это наиболее распространенный формат соревнований, который обычно подразумевается под словом «турнир». Процесс подробно описан ниже:

1. Участникам присваиваются уникальные номера от 1 до $2^N$, и они выстраиваются в ряд в произвольном порядке.
2. Участники в ряду разбиваются на пары по двое, начиная с начала ряда. Каждая пара проводит матч один на один, и проигравший выбывает из ряда. После того как все пары сыграют, количество участников в ряду сокращается вдвое.
3. Таким образом, если повторить процесс 2 ровно $N$ раз, останется только один участник, который и становится победителем турнира.

Турнир с выбыванием часто представляется в виде сетки в форме бинарного дерева, как показано ниже.

Рисунок K.1: Пример сетки турнира с $2^3 = 8$ участниками

Организаторы турнира, включая Хеа, следили за всеми матчами и записывали результаты в общий документ. Однако из-за того, что результаты вносили многие люди одновременно, записи стали совершенно нечитаемыми. Более того, подсчитав количество матчей после окончания турнира, организаторы с ужасом обнаружили, что один матч был пропущен.

Помогите организаторам, которые слишком устали от проведения турнира и не имеют сил разобраться с этой ситуацией, найти пропущенный матч.

Входные данные

В первой строке дано целое число $N$ ($2 \le N \le 20$).

В следующих $2^N - 2$ строках даны по два целых числа $a_i$ и $b_i$, разделенных пробелом, представляющих результат каждого матча. Это означает, что в матче между участником $a_i$ и участником $b_i$ победил участник $a_i$.

Гарантируется, что входные данные представляют собой запись полного турнира, в которой пропущен ровно один матч. Иными словами, не существует таких входных данных, для которых невозможно было бы восстановить корректную историю турнира при любом предположении о результате пропущенного матча.

Выходные данные

Выведите результат пропущенного матча в том же формате, что и во входных данных (два целых числа). Если существует несколько возможных вариантов результата пропущенного матча, выведите все возможные ответы, по одному в строке. При этом сначала выводите варианты в порядке возрастания номера победителя, а если номера победителей совпадают — в порядке возрастания номера проигравшего.

Примеры

Пример 1

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

6 2

Пример 2

2
3 4
1 2

1 3
3 1

Примечание

Сетка турнира для первого примера соответствует рисунку, приведенному в условии.

Во втором примере, где участвовали $2^2 = 4$ человека, пропущен финал. Поскольку невозможно определить, кто стал победителем финала, выводятся оба возможных варианта.