Ви граєте в гру, що складається з \(n\) планет. Кожна планета має телепорт на іншу планету (або на саму планету).

Вам потрібно обробити \(q\) запитів такого вигляду:

• Ви зараз на планеті \(a\) і хочете досягти планети \(b\). Яка мінімальна кількість телепортацій?

Обмеження

• \(1≤n,q≤2⋅10^5\)
• \(1≤a,b≤n\)

Формат вхідних даних

Перший рядок містить два цілі числа \(n\) і \(q\): кількість планет і запитів. Планети пронумеровані \(1,2,…,n\).

Другий рядок містить \(n\) цілих чисел \(t_1 ​ ,t_2 ​ ,…,t_n\) ​ : для кожної планети пункт призначення телепортатора.

Нарешті, є \(q\) рядків, що описують запити. Кожен рядок містить два цілих числа \(a\) і \(b\): ви зараз на планеті \(a\) і хочете досягти планети \(b\).

Формат вихідних даних

Для кожного запиту виведіть мінімальну кількість телепортацій. Якщо неможливо дістатися до місця призначення, виведіть −1.

Приклад вхідних даних

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

Приклад вихідних даних

1
2
-1