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