Koulussa on on n oppilasta, jotka on numeroitu 1,2,\ldots,n. Pian järjestetään tanssiaiset, joissa oppilaat muodostavat n/2 paria.

Justiina on suunnitellut tanssiaiset ja laatinut listan tanssipareista. Listalla on n/2 paria ja jokainen oppilas kuuluu tasan yhteen pariin.

Kotivalo on tehnyt kuitenkin pienen kepposen ja lisännyt johonkin kohtaan listaa ylimääräisen parin. Tehtäväsi on etsiä tämä pari.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: oppilaiden määrä.

Sitten syötteessä on n/2+1 riviä: Justiinan suunnitelma, jossa on mukana Kotivalon lisäämä pari. Jokaisella rivillä on kaksi eri kokonaislukua väliltä 1,2,\ldots,n.

Tuloste

Tulosta Kotivalon lisäämä rivi samalla tavalla kuin syötteessä. Voit olettaa, että rivi on mahdollista selvittää yksikäsitteisesti.

Esimerkki

Syöte:

8
7 3
6 4
4 8
2 5
6 1

Tuloste:

6 4

Osatehtävä 1 (35 pistettä)

• 2 \le n \le 100

Osatehtävä 2 (65 pistettä)

• 2 \le n \le 10^5