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 12161\ldots 2^{16}, ja jokaisessa kohdassa on arvo väliltä 0655350\ldots 65535.

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

Syöte

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

Seuraavat nn riviä sisältävät päivitykset, eli luvut aa ja bb, joka tarkoittaa että muistin kohdan aa arvoksi tulee bb.

Tuloste

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

Rajat

  • 1n1051 \leq n \leq 10^5
  • 1a2161 \leq a \leq 2^{16}
  • 0b655350 \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