Problem A
Ball

Mynd fengin af commons.wikimedia.org

Það er ball í skólanum á morgun og allir $n$ nemendurnir eru skráðar á ballið. Nemendurnir eru númeraðir með tölunum $1$ uppí $n$. Nemendurnir eru skráðir á ballið í pörum og því var skráningarlistinn með $\frac{n}{2}$ línur. Því kemur hver tala fyrir nákvæmlega einu sinni í $\frac{n}{2}$ pörunum. Ó nei! Einhver hefur komist í skráningarlistann og bætt við einu pari. Gefin öll $\frac{n}{2} + 1$ pörin á skráningarlistanum getur þú fundið hvaða par þarf að fjarlægja til að leiðrétta listann?

Inntak

Fyrsta línan inniheldur eina slétta heiltölu $n$ ($2 \leq n \leq 2 \cdot 10^5$), fjöldi nemenda. Næst fylgja $\frac{n}{2} + 1$ línur. Hver lína inniheldur tvær heiltölur $a_ i, b_ i$ ($1 \leq a_ i, b_ i \leq n$), sem tákna par.

Úttak

Skrifið út parið $(a, b)$ sem bætt var við. Það skal skrifa út heiltölurnar $a$ og $b$ aðskilnar með bili þannig að $a < b$.

Stigagjöf

10
1 2
3 5
4 8
6 7
4 7
9 10

4 7

2
2 1
1 2

1 2