1009. 自乘

题目描述

给定一个长度为 $n$ 的数组 $a$（$1 \le a_i \le n$），定义自乘操作：将 $a$ 映射为新数组 $c$，其中 $c_i = a_{a_i}$。

记初始数组为 $a_0 = a$，每次操作后 $a_{i+1}$ 为 $a_i$ 的自乘。即：

$$a_0 = a,\qquad a_{i+1}[j] = a_i\big[a_i[j]\big]\quad(1 \le j \le n)$$

给定初始数组 $a$ 和目标数组 $b$，求最小的非负整数 $k$ 使得 $a_k = b$。若无法得到，输出 $-1$。

输入格式

第一行一个整数 $t$（$1 \le t \le 2000$），表示测试用例数。

每组测试用例包含三行：

• 第一行一个整数 $n$（$1 \le n \le 1000$），表示数组长度。
• 第二行 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。
• 第三行 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le n$）。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试用例，输出一行一个整数 $k$。若不存在这样的 $k$，则输出 $-1$。

样例输入

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

样例输出

3
1
0
-1

提示

对于第一组样例，$a_0 = [2,3,4,5,1]$。

• 第 1 次自乘后：$a_1 = [3,4,5,1,2]$；
• 第 2 次自乘后：$a_2 = [5,1,2,3,4]$；
• 第 3 次自乘后：$a_3 = [4,5,1,2,3] = b$，故 $k=3$。

对于第三组样例，$a_0 = [1,2]$，已等于 $b$，无需操作，$k=0$。

对于第四组样例，数组 $a$ 一直是 $[1,2]$，无法达到 $b$，输出 $-1$。

来源：2026杭电多校-测试专用（电子科大） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1233&pid=1009