D. Бесконечный путь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана цветная перестановка $$$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]]$$$. Более того, можно определить степень $$$k$$$ перестановки $$$p$$$, как $$$p^k=\underbrace{p \times p \times \dots \times p}_{k \text{ times}}$$$.

Найдите такое минимальное $$$k > 0$$$, что $$$p^k$$$ содержит хотя бы один бесконечный путь (т.е. существует позиция $$$i$$$ в $$$p^k$$$, такая, что последовательность, начинающаяся с $$$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$$$ при $$$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$$$ содержит хотя бы один бесконечный путь.

Пример
Входные данные
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
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$$$.