Приєднання пар
Правила повітряного руху в Нлогонії вимагають, щоб кожне місто мало рівно один зареєстрований виліт в інше місто. Пасажири можуть використовувати цей рейс лише в зазначеному напрямку, тобто може бути зареєстрований рейс з міста X в місто Y, але не навпаки. Таким чином, кількість зареєстрованих рейсів дорівнює кількості міст. Це правило, як можна собі уявити, робить повітряні подорожі дещо складними, але традиції та суворі постанови Королеви роблять будь-які зміни важкими. Крім того, деякі компанії навіть отримують прибуток від проблем, викликаних цим правилом.
Асоціація з підбору пар (ACM) запускає новий сервіс, щоб допомогти клієнтам знайти своїх довгострокових супутників життя: Інтернет-програму з'єднання пар (ICPC). Сервіс полягає у обчисленні мінімальної загальної кількості рейсів, які парі необхідно здійснити, щоб зустрітися один з одним (можливо, в місті, де жоден з них не живе). Припускаючи, що початкові міста пари — це A і B, агентство намагатиметься знайти місто C таке, що C досяжне повітряним транспортом як з A, так і з B, і сума кількості рейсів, необхідних для того, щоб дістатися з A в C, і кількості рейсів, необхідних для того, щоб дістатися з B в C, мінімальна. Зверніть увагу, що C може дорівнювати A або B або обом.
Вам буде надано список усіх доступних рейсів і список запитів, що складається з пар міст, де живуть члени пари. Для кожного запиту ви повинні обчислити мінімальну загальну кількість рейсів, необхідних для їх зустрічі.
Вхідні дані
Кожен тестовий випадок описується кількома рядками. Перший рядок містить ціле число N, що представляє кількість міст (2 ≤ N ≤ 10^5). Міста ідентифікуються різними цілими числами від 1 до N. Другий рядок містить N цілих чисел F_i, де F_{i } вказує, що зареєстрований виліт з міста i спрямований в місто F_i (1 ≤ F_i ≤ N, F_i ≠ i для i = 1, 2, ..., N). Третій рядок містить ціле число Q, що представляє кількість запитів (1 ≤ Q ≤ 10^5). Кожен з наступних Q рядків описує запит двома цілими числами A і B, що вказують початкові міста пари (1 ≤ A, B ≤ N). В межах кожного тестового випадку, якщо можливо дістатися повітряним транспортом з міста X в місто Y, максимальна кількість рейсів, необхідних для цього, становить 10^4.
Вихідні дані
Для кожного тестового випадку виведіть Q рядків. У i-му рядку напишіть ціле число, яке є відповіддю на i-й запит. Якщо відповідна пара може зустрітися повітряним транспортом, напишіть мінімальну загальну кількість рейсів, які пара повинна здійснити, щоб зустрітися один з одним; якщо парі неможливо зустрітися повітряним транспортом, напишіть число '-1'.