全大プロ（全国大学生プログラミング大会サークル連合）は、3年前に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

出力 1

6 2

入力 2

2
3 4
1 2

出力 2

1 3
3 1

注記

最初の例の対戦表は、問題文で与えられた図と同じである。

二番目の例は $2^2 = 4$ 名が参加した大会で決勝戦が漏れた記録であり、決勝戦の勝者が誰であるか不明であるため、二つの可能性をすべて出力する。