Code Submission Evaluation System Login

IOI-leiri 2016

Teleportit II


Task | Statistics


CSES - Teleportit IICSES - Teleportit II

Time limit:1.00 s Memory limit:128 MB

Uolevi pelaa peliä, jossa on $n$ tasoa. Jokaisella tasolla on teleportti, josta pääsee jollekin toiselle tasolle.

Tehtäväsi on vastata joukkoon kyselyitä. Jokaisessa kyselyssä Uolevi haluaa päästä tasolta $a$ tasolle $b$, ja tehtäväsi on selvittää, mikä on pienin määrä teleportteja, joiden kautta Uolevin tavoite onnistuu.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $q$: tasojen määrä ja kyselyiden määrä. Tasot on numeroitu kokonaisluvuin $1,2,\ldots,n$.

Seuraavalla rivillä on $n$ lukua $t_1,t_2,\ldots,t_n$. Luku $t_i$ kertoo, mille tasolle tason $i$ teleportista pääsee.

Lopuksi syötteessä on $q$ riviä, jotka kuvaavat kyselyt. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: Uolevi haluaa päästä tasolta $a$ tasolle $b$. Uolevi haluaa aina päästä toiselle tasolle kuin mistä aloittaa eli $a \neq b$.

Tuloste

Tulosta jokaiseen kyselyyn pienin määrä, monenko teleportin kautta Uolevin täytyy kulkea, jotta hän pääsee tasolta $a$ tasolle $b$. Jos tämä ei ole mahdollista, tulosta $-1$.

Rajat
Esimerkki

Syöte:
4 3
2 4 2 3
1 4
2 1
4 3


Tuloste:
2
-1
1