Estás jugando a un juego compuesto por ~n~ planetas. Cada planeta tiene un teletransportador a otro planeta (o al propio planeta). Tienes que procesar ~q~ consultas de la forma: Ahora estás en el planeta ~a~ y quieres llegar al planeta ~b~. ¿Cuál es el número mínimo de teletransportaciones?

Entrada

La primera línea de entrada contiene dos números enteros ~n~ y ~q~: el número de planetas y de consultas. Los planetas se numeran ~1,2,\ldots,n~. La segunda línea contiene ~n~ enteros ~t_1,t_2,\ldots,t_n~: para cada planeta, el destino del teletransportador. Por último, hay ~q~ líneas que describen las consultas. Cada línea tiene dos enteros ~a~ y ~b~: ahora estás en el planeta ~a~ y quieres llegar al planeta ~b~.

Salida

Para cada consulta, imprime el número mínimo de teletransportaciones. Si no es posible alcanzar el destino, imprime ~-1~.

Restricciones

• ~1 \leq n, q \leq 2 \cdot 10^5~
• ~1 \leq a,b \leq n~

Ejemplo de Entrada

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

Ejemplo de Salida

1
2
-1