#P17133. 自乘

自乘

1009. 自乘

题目描述

给定一个长度为 nn 的数组 aa(1≤ai≤n1 \le a_i \le n),定义自乘操作:将 aa 映射为新数组 cc,其中 ci=aaic_i = a_{a_i}。

记初始数组为 a0=aa_0 = a,每次操作后 ai+1a_{i+1} 为 aia_i 的自乘。即:

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

给定初始数组 aa 和目标数组 bb,求最小的非负整数 kk 使得 ak=ba_k = b。若无法得到,输出 −1-1。

输入格式

第一行一个整数 tt(1≤t≤20001 \le t \le 2000),表示测试用例数。

每组测试用例包含三行:

  • 第一行一个整数 nn(1≤n≤10001 \le n \le 1000),表示数组长度。
  • 第二行 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n(1≤ai≤n1 \le a_i \le n)。
  • 第三行 nn 个整数 b1,b2,…,bnb_1, b_2, \dots, b_n(1≤bi≤n1 \le b_i \le n)。

保证所有测试用例的 nn 之和不超过 10610^6。

输出格式

对于每组测试用例,输出一行一个整数 kk。若不存在这样的 kk,则输出 −1-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

提示

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

  • 第 1 次自乘后:a1=[3,4,5,1,2]a_1 = [3,4,5,1,2];
  • 第 2 次自乘后:a2=[5,1,2,3,4]a_2 = [5,1,2,3,4];
  • 第 3 次自乘后:a3=[4,5,1,2,3]=ba_3 = [4,5,1,2,3] = b,故 k=3k=3。

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

对于第四组样例,数组 aa 一直是 [1,2][1,2],无法达到 bb,输出 −1-1。

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