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

Обмеження: 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\) гнідий і вороний жеребець не можуть опинитися на одній ділянці.