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

• $1 \le n,q \le 10^5$
• $1 \le a,b \le n$

Esimerkki

Syöte:

4 3
2 4 2 3
1 4
2 1
4 3

Tuloste:

2
-1
1