CF1690F Shifting String

Polycarp 找到了一串字符串 $s$ 和一个排列 $p$。它们的长度相同，均为 $n$。 一个长度为 $n$ 的排列，是一个长度为 $n$ 的数组，其中每个整数 $1$ 到 $n$ 恰好出现一次。例如，$[1, 2, 3]$ 和 $[4, 3, 5, 1, 2]$ 是排列，但 $[1, 2, 4]$、$[4, 3, 2, 1, 2]$ 和 $[0, 1, 2]$ 不是。 每进行一次操作，他可以用排列 $p$ 作用于字符串 $s$，即将 $s$ 替换为新字符串 $new$，其中对于任意 $i$ 满足 $1 \le i \le n$，都有 $new_i = s_{p_i}$。例如，若 $s=wmbe$，$p = [3, 1, 4, 2]$，操作后字符串变为 $s=s_3 s_1 s_4 s_2=bwem$。 Polycarp 想知道，最少经过多少次操作后，字符串才会第一次变回最初的样子。由于可能需要很多次操作，他请求你帮忙计算。 可以证明，所需的操作次数总是存在。答案可能很大，请使用 64 位整数类型。

输入的第一行包含一个整数 $t$（$1 \le t \le 5000$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 200$），表示字符串和排列的长度。 每个测试用例的第二行包含一个长度为 $n$ 的字符串 $s$，仅包含小写拉丁字母。 每个测试用例的第三行包含 $n$ 个整数，表示排列 $p$（$1 \le p_i \le n$），所有 $p_i$ 互不相同。

输出 $t$ 行，每行一个整数，表示对应测试用例的答案——使字符串 $s$ 恢复为初始状态所需的最小操作次数。

在第一个样例中，操作不会改变字符串，因此只需 $1$ 次操作字符串就会恢复原状。 在第二个样例中，字符串变化如下： - $s$ = babaa - $s$ = abaab - $s$ = baaba - $s$ = abbaa - $s$ = baaab - $s$ = ababa 由 ChatGPT 4.1 翻译