전국 대학생 프로그래밍 대회 동아리 연합 토너먼트

문제

전대프연은 $3$ 년 전에 UCPC를 토너먼트 방식으로 바꾸겠다고 선언한 적이 있지만, 너무 큰 변화를 감행하느라 많은 시행착오를 겪었다. 올해 전대프연의 회장을 맡은 혜아는 내부 문서들을 읽다가 이 대회의 준비 기록을 발견하고, 토너먼트 방식의 대회를 다시 열어 보기로 결심했다.

운이 좋게도 이번 UCPC에는 정확히 $2^{N}$ 명의 참가자가 참가했기 때문에, 혜아는 싱글 엘리미네이션 방식으로 아주 깔끔하게 대회를 진행할 수 있게 되었다. 이는 일반적으로 ‘토너먼트’라고 할 때 가장 먼저 떠오르는 대회 방식으로, 과정을 자세히 설명하면 다음과 같다.

참가자들에게 $1$ 번부터 $2^{N}$ 번까지의 서로 다른 시드 번호를 부여하고, 임의의 순서로 한 줄로 나열한다.
줄에 속해 있는 참가자들을 앞에서부터 두 명씩 짝을 짓는다. 서로 짝지어진 두 참가자는 일대일 경기를 진행하고, 여기서 패배한 참가자는 줄에서 떠난다. 이렇게 모든 짝이 경기를 진행하고 나면 줄에 남는 참가자 수는 이전의 절반이 됨을 알 수 있다.
따라서 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$ 번 참가자가 이겼음을 의미한다.

주어지는 입력은 올바른 전체 경기 기록에서 경기 하나가 누락된 기록임이 보장된다. 즉, 누락된 경기의 결과를 어떻게 추측하더라도 올바른 기록이 만들어지지 않는 입력은 주어지지 않는다.

출력

누락된 경기의 결과를 입력과 같은 형식으로 두 개의 정수로 출력한다. 가능한 경기 결과가 여러 가지일 경우는 모든 가능한 답을 한 줄에 하나씩 출력한다. 이때 승자의 번호가 작은 것부터, 그런 것이 여러 가지라면 그중 패자의 번호가 작은 것부터 출력하도록 한다.