CSES - Datatähti Open 2018 - 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.


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$.


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


7 3
6 4
4 8
2 5
6 1

6 4

Subtask 1 (35 points)
  • $2 \le n \le 100$
Subtask 2 (65 points)
  • $2 \le n \le 10^5$