← 返回题目列表

Codeforces · 1327/D

D. 无限路径

中文机器翻译题面 查看原题

给你一个彩色排列 $$$p_1, p_2, \dots, p_n$$$。排列的第 $$$i$$$ 元素的颜色为 $$$c_i$$$。

让我们将无限路径定义为无限序列 $$$i, p[i], p[p[i]], p[p[p[i]]] \dots$$$,其中所有元素都具有相同的颜色 ($$$c[i] = c[p[i]] = c[p[p[i]]] = \dots$$$)。

我们还可以将排列 $$$a$$$ 和 $$$b$$$ 的乘法定义为排列 $$$c = a \times b$$$ 其中 $$$c[i] = b[a[i]]$$$。此外,我们可以将排列$$$p$$$的幂$$$k$$$定义为$$$p^k=\underbrace{p \times p \times \dots \times p}_{k \text{ times}}$$$。

找到最小值 $$$k > 0$$$,使得 $$$p^k$$$ 至少有一条无限路径(即 $$$p^k$$$ 中有一个位置 $$$i$$$,使得从 $$$i$$$ 开始的序列是无限路径)。

可以证明答案总是存在的。

输入

第一行包含单个整数 $$$T$$$ ($$$1 \le T \le 10^4$$$) — 测试用例的数量。

接下来的 $$$3T$$$ 行包含测试用例 — 每三行一个。第一行包含单个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 排列的大小。

第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$, $$$p_i \neq p_j$$$ for $$$i \neq j$$$) — 排列 $$$p$$$。

第三行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — 排列元素的颜色。

保证$$$n$$$的总和不超过$$$2 \cdot 10^5$$$。

输出

打印 $$$T$$$ 整数 — 每个测试用例一个。对于每个测试用例,打印最小值 $$$k > 0$$$,使得 $$$p^k$$$ 至少有一条无限路径。

示例

输入 #1

3
4
1 3 4 2
1 2 2 3
5
2 3 4 5 1
1 2 3 4 5
8
7 4 5 6 1 8 3 2
5 3 6 4 7 5 8 4

输出 #1

1
5
2

注意

在第一个测试用例中, $$$p^1 = p = [1, 3, 4, 2]$$$ 并且从 $$$1$$$ 开始的序列: $$$1, p[1] = 1, \dots$$$ 是无限路径。

在第二个测试用例中,$$$p^5 = [1, 2, 3, 4, 5]$$$ 并且它显然包含多个无限路径。

在第三个测试用例中, $$$p^2 = [3, 6, 1, 8, 7, 2, 5, 4]$$$ 并且从 $$$4$$$ 开始的序列: $$$4, p^2[4]=8, p^2[8]=4, \dots$$$ 是一条无限路径,因为 $$$c_4 = c_8 = 4$$$。