Перестановочный логарифм
Сложная
Ограничение по времени выполнения 1 секунда
Ограничение по использованию памяти 256 мегабайт
Пусть заданы две перестановки p = (p_1, p_2, ..., p_N) и q = (q_1, q_2, ..., q_N) чисел от 1 до N.
Требуется найти такую минимальную целую неотрицательную степень d, что p^d = q (то есть d-кратное применение перестанвоки p к массиву (1, 2, ..., N) приведёт к массиву q).
Входные данные
В первой строке входного файла задаётся натуральное число N (1 ≤ N ≤ 2·10^5). Во второй и третьей строках определяются перестановки p и q соответственно. Каждая из этих строк содержит N чисел, определяющих соответствующую перестановку.
Выходные данные
В выходной файл необходимо вывести наименьшее неотрицательное значение d, при котором p^d = q. Если такого числа не существует, выведите -1.
Примеры
Ввод #1
Ответ #1
Отправки 20
Коэффициент принятия 5 %