给你一个彩色排列 $$$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$$$。