题目描述

对于长度为 $n$ 的置换 $A,B$,求是否存在正整数 $k$ 使得 $A^k=B$。
定义置换的乘法为 $(A⋅B)i=A{B_i}$

定义 $A^1=A,A^n=A^{n-1}\cdot A(n>1)$。

输入

输入包含多组数据,以 $\text EOF$ 结尾。

每组数据有三行:

第一行一个整数 $n$。

第二行 $n$ 个整数表示置换 $A$。

第三行 $n$ 个整数表示置换 $B$。

输出

如果存在 $k$ 输出 $\text Yes$ 否则输出 $\text No$。

思路

对于 $A$,我们先找到它内部的所有环。对于一个环,我们能预处理出它的长度偏移量。偏移量即使它和 $B$ 中数字完全对应考虑 $i,j$ 两个环,如果两个环的数能在某一次置换后对应的数等于b中的数,则要求 $del[i]+k\cdot len[i]==del[j]+p\cdot len[j]$。

代码