CSES - Datatähti 2018 loppu - Tanssiaiset
  • Time limit: 1.00 s
  • Memory limit: 512 MB
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$