CSES - Silmukka
  • Time limit: 4.00 s
  • Memory limit: 128 MB

Uolevin algoritmi on ollut käynnissä jo kolme kuukautta, ja siksi hän on alkanut epäillä sen jääneen ikuiseen silmukkaan. Uolevi suorittaa algoritmia uudella tietokoneellaan, jossa on 128 kilotavun muisti. Uolevi tietää, että ohjelma on jäänyt silmukkaan, jos täsmälleen sama muistin sisältö toistuu kahdesti suorituksen aikana. Sinun täytyy toteuttaa algoritmi, joka tunnistaa, milloin aiemmin esiintynyt muistin tila toistuu ensimmäisen kerran.

Tietokone on 16-bittinen, joten muistia käsitellään taulukkona, jossa on kohdat 1\ldots 2^{16}, ja jokaisessa kohdassa on arvo väliltä 0\ldots 65535.

Ohjelman suorituksen aluksi kaikissa kohdissa on arvo 0. Ohjelmallesi kerrotaan järjestyksessä muistiin tehtävät päivitykset.

Syöte

Ensimmäisellä syötteen rivillä on päivitysten määrä n.

Seuraavat n riviä sisältävät päivitykset, eli luvut a ja b, joka tarkoittaa että muistin kohdan a arvoksi tulee b.

Tuloste

Tulosta pienin i siten, että i. päivityksen jälkeen muistin tila on sama kuin aikaisemmin. Mikäli tällaista i ei ole olemassa, tulosta YAY.

Rajat

  • 1 \leq n \leq 10^5
  • 1 \leq a \leq 2^{16}
  • 0 \leq b \leq 65535

Huomautus

Joissain testitapauksissa samaa muistin tilaa voi seurata eri päivitys.

Esimerkki

Syöte:

6
1 5
4 7
8 3
4 0
8 0
5 4

Tuloste:

5