Зустріч на іподромі

Обмеження: 4 сек., 512 МіБ

На фермі Зеника та Марічки є іподром, що складається з $n$ ділянок, пронумерованих від $1$ до $n$. Ділянки з’єднані односторонніми доріжками — з кожної ділянки виходить рівно одна доріжка. Доріжка з ділянки $i$ веде до ділянки $f_i$ (якщо $f_i = i$, це означає, що доріжка починається та закінчується в тій самій ділянці $i$).

Вам потрібно відповісти на $q$ таких запитів.

• Є двоє жеребців: гнідий та вороний. Гнідий жеребець стоїть на ділянці $u$, а вороний — на ділянці $v$. За одну хвилину кожен кінь може залишитися на місці або доріжкою перейти до тієї ділянки іподрому, куди вона веде. Зауважте, що з кожної ділянки є завжди одна доріжка. Порахуйте, за який найменший час обоє жеребців можуть опинитися на тій самій ділянці іподрому, або скажіть, що це неможливо.

Вхідні дані

У першому рядку задано два цілих числа $n$ та $q$ — кількість ділянок іподрому та кількість запитів.

У другому рядку задано $n$ цілих чисел $f_i$, що описують доріжки між ділянками іподрому.

У наступних $q$ рядках задано по два цілих числа $u$ та $v$ — початкові ділянки гнідого й вороного жеребців.

Вихідні дані

У $q$ рядках виведіть по одному цілому числу — найменший час у хвилинах, за який обидва жеребці можуть опинитися на тій самій ділянці, або -1, якщо це неможливо.

Обмеження

$1 \le n, q \le 3 \cdot 10^5$,

$1 \le f_i, u, v \le n$.

Оцінювання складається з таких блоків:

• по 1 балу за кожен приклад з умови,

• 7 балів: $f_i = i$,

• 14 балів: $n, q \le 10^3$,

• 16 балів: для кожної вершини $v$ існує вершина $u$ така що $f_u = v$,

• 21 бал: $f_i \le i$,

• 26 балів: з усіх вершин можна дійти до вершини 1,

• 14 балів: без додаткових обмежень.

Бали за блок ви отримаєте, тільки якщо ваша програма пройде всі тести з блоку.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
8 5 2 3 1 2 4 7 6 7 1 5 6 7 6 8 2 5 4 7	2 1 1 2 -1

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 4 2 3 4 5 6 7 1 2 3 2 5 2 6 7 7	1 3 3 0

Примітки

У першому прикладі для запиту $u = 1, v = 5$ відповідь дорівнює $2$. Тобто якщо гнідий жеребець починає на ділянці $1$, а вороний — на ділянці $5$, то вони можуть опинитися на одній ділянці за дві хвилини.

• За першу хвилину гнідий жеребець переходить з ділянки $1$ на ділянку $2$, а вороний — з ділянки $5$ на ділянку $4$.

• За другу хвилину вороний жеребець переходить з ділянки $4$ на ділянку $2$, а гнідий стоїть на місці на ділянці $2$.

Для запиту $u = 4, v = 7$ гнідий і вороний жеребець не можуть опинитися на одній ділянці.