무도회

commons.wikimedia.org에서 가져온 이미지

내일 학교에서 무도회가 열리며, 학생 $n$명 전원이 무도회에 등록되어 있다. 학생들에게는 $1$부터 $n$까지의 번호가 매겨져 있다. 학생들은 두 명씩 짝을 지어 무도회에 등록되었으므로, 등록 명단에는 $\frac{n}{2}$개의 줄이 있었다. 따라서 각 번호는 $\frac{n}{2}$개의 쌍에 정확히 한 번씩 등장한다. 이런! 누군가가 등록 명단에 접근하여 쌍 하나를 추가했다. 등록 명단의 $\frac{n}{2} + 1$개 쌍이 모두 주어질 때, 명단을 바로잡기 위해 어떤 쌍을 제거해야 하는지 찾을 수 있는가?

채점

그룹 | 점수 | 제한

1 | 40 | $2 \leq n \leq 200$

2 | 30 | $2 \leq n \leq 5000$

3 | 30 | 추가 제한 없음

첫 번째 줄에는 학생 수를 나타내는 하나의 짝수 정수 $n$ ($2 \leq n \leq 2 \cdot 10^5$)가 주어진다. 다음 $\frac{n}{2} + 1$개의 줄이 이어진다. 각 줄에는 하나의 쌍을 나타내는 두 정수 $a_i, b_i$가 주어진다.

추가된 쌍 $(a, b)$를 출력한다. 정수 $a$와 $b$를 공백으로 구분하여 $a < b$가 성립하도록 출력해야 한다.