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

Postitoimistossa otettiin käyttöön uusi lajittelukone, mutta tämän jälkeen kirjeitä alkoi mennä vääriin paikkoihin.

Eräänä päivänä jokaiselle postipiirin asukkaalle oli määrä jakaa yksi kirje. Jokainen asukas saikin kirjeen, mutta ei välttämättä omaansa.

Asukkaat päättivät vaihtaa kirjeet seuraavasti: Jokaisena seuraavana päivänä kukin asukas voi tavata jonkin toisen asukkaan ja vaihtaa kirjeitä hänen kanssaan. Sama asukas ei voi vaihtaa kirjeitä monen kanssa samana päivänä.

Kuinka monta päivää tarvitaan siihen, että kaikki ovat saaneet oman kirjeensä, jos asukkaat toimivat optimaalisesti?

Syöte

Syöteen ensimmäisellä rivillä on kokonaisluku n: asukkaiden määrä. Asukkaat on numeroitu kokonaisluvuin 1,2,\ldots,n.

Syötteen seuraavalla rivillä on n lukua: jokaisen kirjeen oikea vastaanottaja.

Syötteen seuraavalla rivillä on n lukua: jokaisen kirjeen todellinen vastaanottaja.

Jokainen luku väliltä 1,2,\ldots,n esiintyy tarkalleen kerran kummallakin kahdella viimeisellä rivillä.

Tuloste

Ohjelmasi tulee tulostaa, kuinka monen päivän jälkeen jokainen on saanut oman kirjeensä, jos asukkaat toimivat optimaalisesti

Rajat

  • 1 \le n \le 10^5

Esimerkki

Syöte:

5
1 4 5 2 3
5 2 1 3 4

Tuloste:

2

Selitys: Ensimmäisenä päivänä asukkaat 1 ja 5 tapaavat toisensa, samoin asukkaat 2 ja 3. Tämän seurauksena asukkaat 1, 2 ja 5 saavat oikean kirjeen. Toisena päivänä asukkaat 3 ja 4 tapaavat toisensa, minkä jälkeen kaikilla on oikea kirje.