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\le n\le 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\le a_i,b_i\le 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