The Korean Collegiate Programming Club (KCPC) once announced three years ago that it would switch the UCPC to a tournament format, but it faced many trials and errors due to the magnitude of the change. Hye-ah, who became the president of the KCPC this year, discovered the preparation records for this tournament while reading internal documents and decided to hold a tournament-style competition again.

Fortunately, since exactly $2^N$ participants registered for this year's UCPC, Hye-ah was able to conduct the competition very cleanly using a single-elimination format. This is the competition format that first comes to mind when one thinks of a "tournament," and the process is described in detail as follows:

1. Assign unique seed numbers from 1 to $2^N$ to the participants and arrange them in a line in an arbitrary order.
2. Pair the participants in the line two by two from the front. The two paired participants play a one-on-one match, and the loser leaves the line. It can be seen that after all pairs have played their matches, the number of participants remaining in the line is halved.
3. Therefore, if process 2 is repeated $N$ times, only one participant will remain, and this participant becomes the winner of the competition.

A single-elimination tournament is often represented by a bracket in the shape of a binary tree, as shown below.

Figure K.1: An example of a tournament bracket with $2^3 = 8$ participants

The competition organizers, including Hye-ah, supervised all matches held during the competition and recorded the results in a shared document. However, because many people were scribbling down the results, it became impossible to discern the flow of the competition from these records. Furthermore, after the competition ended, the organizers counted the number of matches and discovered the desperate fact that one match was missing.

On behalf of the organizers, who are too exhausted from running the competition to handle this situation, let's find the one match missing from the records.

Input

The first line contains an integer $N$ ($2 \le N \le 20$).

The next $2^N - 2$ lines each contain two space-separated integers $a_i$ and $b_i$, representing the result of each match. This means that in the match, participant $a_i$ and participant $b_i$ faced each other, and participant $a_i$ won.

It is guaranteed that the input provided is a record of the entire competition with exactly one match missing. In other words, no input will be given where it is impossible to form a valid record regardless of how the missing match result is guessed.

Output

Output the result of the missing match as two integers in the same format as the input. If there are multiple possible match results, output all possible answers, one per line. When doing so, sort the results by the winner's number in ascending order, and if there are multiple results with the same winner, sort them by the loser's number in ascending order.

Examples

Input 1

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

Output 1

6 2

Input 2

2
3 4
1 2

Output 2

1 3
3 1

Note

The bracket for the first example is the same as the figure provided in the problem description.

The second example is a record from a competition with $2^2 = 4$ participants where the final match is missing. Since it is impossible to know who won the final, both possibilities are output.