Code Submission Evaluation System Login

Datatähti Open 2018

Start:N/A
End:N/A
 

Tasks | Scoreboard | Statistics


CSES - Datatähti Open 2018 - School DanceCSES - School Dance

School Dance

Time limit:1.00 s
Memory limit:512 MB

There are $n$ pupils in a school, numbered $1,2,\ldots,n$. There will soon be a dance event where the pupils will form $n/2$ pairs.

Justiina has planned the event and created a list of dance pairs. The list consists of $n/2$ pairs, and each pupil belongs to exactly one pair.

However, Kotivalo has made a little prank and added somewhere in the list an extra pair. Your task is to find this pair.

Input

The first input line contains an integer $n$: the number of pupils.

After this, there are $n/2+1$ lines: Justiina's plan with Kotivalo's addition. Each line contains two distinct integers between $1,2,\ldots,n$.

Output

Print the line added by Kotivalo in the same way as in the input. You can assume that there is only one possible answer.

Example

Input:
8
7 3
6 4
4 8
2 5
6 1


Output:
6 4

Subtask 1 (35 points)
Subtask 2 (65 points)