You are given a colored permutation $p_1, p_2, \dots, p_n$. The $i$-th element of the permutation has color $c_i$.

Let's define an infinite path as infinite sequence $i, p[i], p[p[i]], p[p[p[i]]] \dots$ where all elements have same color ($c[i] = c[p[i]] = c[p[p[i]]] = \dots$).

We can also define a multiplication of permutations $a$ and $b$ as permutation $c = a \times b$ where $c[i] = b[a[i]]$. Moreover, we can define a power $k$ of permutation $p$ as $p^k=\underbrace{p \times p \times \dots \times p}_{k \text{ times}}$.

Find the minimum $k > 0$ such that $p^k$ has at least one infinite path (i.e. there is a position $i$ in $p^k$ such that the sequence starting from $i$ is an infinite path).

It can be proved that the answer always exists.


-----Input-----

The first line contains single integer $T$ ($1 \le T \le 10^4$) — the number of test cases.

Next $3T$ lines contain test cases — one per three lines. The first line contains single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of the permutation.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$, $p_i \neq p_j$ for $i \neq j$) — the permutation $p$.

The third line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$) — the colors of elements of the permutation.

It is guaranteed that the total sum of $n$ doesn't exceed $2 \cdot 10^5$.


-----Output-----

Print $T$ integers — one per test case. For each test case print minimum $k > 0$ such that $p^k$ has at least one infinite path.


-----Example-----
Input
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

Output
1
5
2



-----Note-----

In the first test case, $p^1 = p = [1, 3, 4, 2]$ and the sequence starting from $1$: $1, p[1] = 1, \dots$ is an infinite path.

In the second test case, $p^5 = [1, 2, 3, 4, 5]$ and it obviously contains several infinite paths.

In the third test case, $p^2 = [3, 6, 1, 8, 7, 2, 5, 4]$ and the sequence starting from $4$: $4, p^2[4]=8, p^2[8]=4, \dots$ is an infinite path since $c_4 = c_8 = 4$.

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Complete search

Number theory

Mathematics
Skill types: Complete search

Starter code:

Solutions:
t = int(input())

def find_loops():
	seen = [0] * n
	loops = []
	for i in range(n):
		if seen[i]:
			continue
		j = i
		l = []
		while 1:
			if seen[j]:
				break
			l.append(j)
			seen[j] = 1
			j = p[j] - 1
		loops.append(l)
	return loops

def get_factors(number):
	factors = []
	i = 1
	while i ** 2 <= number:
		if number % i == 0:
			factors.append(i)
			if i ** 2 != number:
				factors.append(int(number / i))
		i = i + 1
	return factors

def process_loop(loop):
	length = len(loop)
	min_factor = length
	for i in get_factors(length):
		is_ok = [1] * i
		for j in range(length):
			if c[loop[j]] != c[loop[j % i]]:
				is_ok[j % i] = 0
		for a in is_ok:
			if a == 1:
				min_factor = min(min_factor, i)
	return min_factor
for x in range(t):
	n = int(input())
	p = list(map(int, input().strip().split()))
	c = list(map(int, input().strip().split()))
	loops = find_loops()
	min_k = n
	for loop in loops:
		min_k = min(min_k, process_loop(loop))
		if min_k == 1:
			break
	print(min_k)


from sys import stdin, stdout
import math

def divisor(n):
	i = 1
	l = []
	l.append(i)
	while i <= math.sqrt(n):
		if n % i == 0:
			if i == n / i:
				l.append(i)
			else:
				l.append(i)
				l.append(n // i)
		i += 1
	l.sort()
	return l

def solve(d, k, c, n):
	kmin = n
	for i in range(k):
		st = len(d[i])
		if kmin > st:
			kmin = st
		l = divisor(st)
		for i1 in l:
			length = st // i1
			j = -1
			for i2 in range(i1):
				j += 1
				ind = j
				cnt = length - 1
				ch = 1
				while cnt:
					if c[d[i][ind]] != c[d[i][(ind + i1) % st]]:
						ch = 0
						break
					ind = (ind + i1) % st
					cnt -= 1
				if ch == 1:
					if kmin > i1:
						kmin = i1
					break
			if kmin <= i1:
				break
	return kmin

def main():
	t = int(input())
	while t:
		n = int(input())
		l = list(map(int, input().split()))
		c = list(map(int, input().split()))
		l.insert(0, 0)
		c.insert(0, 0)
		presnt = {}
		parent = {}
		d = {}
		for i in range(1, n + 1):
			presnt[i] = 1
			parent[l[i]] = i
		l = n
		k = 0
		while l > 0:
			if d.get(k, -1) == -1:
				d[k] = []
			for i in presnt:
				j = i
				break
			j1 = parent[j]
			del presnt[j]
			d[k].append(j1)
			l -= 1
			while j != j1:
				del presnt[j1]
				j1 = parent[j1]
				d[k].append(j1)
				l -= 1
			k += 1
		kmin = solve(d, k, c, n)
		print(kmin)
		t -= 1
main()


import sys

def input():
	return sys.stdin.buffer.readline()[:-1]
t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	col = list(map(int, input().split()))
	p = [x - 1 for x in p]
	visited = [False for _ in range(n)]
	cycles = []
	for i in range(n):
		if not visited[i]:
			tmp = [i]
			visited[i] = True
			while p[tmp[-1]] != tmp[0]:
				visited[p[tmp[-1]]] = True
				tmp.append(p[tmp[-1]])
			cycles.append(tmp)
	ans = n
	for cy in cycles:
		l = len(cy)
		ans = min(ans, l)
		divs = []
		i = 1
		while i * i <= l:
			if l % i == 0:
				divs.append(i)
				if i * i != l and i > 1:
					divs.append(l // i)
			i += 1
		for d in divs:
			for i in range(d):
				same = True
				for j in range(i + d, l, d):
					if col[cy[i]] != col[cy[j]]:
						same = False
				if same:
					ans = min(ans, d)
	print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
from math import sqrt

def primeFactor(n):
	(ret, i, d, sq) = ({}, 2, 2, int(sqrt(n)) + 1)
	while i < 4:
		k = 0
		while n % i == 0:
			(n, k) = (n // i, k + 1)
			(ret[i], sq) = (k, int(sqrt(n)) + 1)
		i = i * 2 - 1
	while i <= sq:
		k = 0
		while n % i == 0:
			(n, k) = (n // i, k + 1)
			(ret[i], sq) = (k, int(sqrt(n)) + 1)
		(i, d) = (i + d, d ^ 6)
	if n > 1:
		ret[n] = 1
	return ret

def divisors(N):
	pf = primeFactor(N)
	ret = [1]
	for p in pf:
		prev = ret[:]
		q = 1
		for i in range(1, pf[p] + 1):
			q *= p
			for r in prev:
				ret.append(r * q)
	return sorted(ret)

def chk(X):
	n = len(X)
	XX = X * 2
	mi = 1 << 30
	for d in divisors(n):
		if d >= mi:
			break
		for i in range(d):
			for j in range(i, n + i, d):
				if XX[j] != XX[j + d]:
					break
			else:
				mi = min(mi, d)
	return mi
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(a) - 1 for a in input().split()]
	C = [int(a) - 1 for a in input().split()]
	done = [0] * N
	L = []
	for i in range(N):
		if done[i]:
			continue
		t = [C[i]]
		j = A[i]
		while j != i:
			t.append(C[j])
			done[j] = 1
			j = A[j]
		L.append(t)
	print(min([chk(a) for a in L]))


from sys import stdin, stdout

def main():
	t = int(stdin.readline())
	for _ in range(t):
		n = int(stdin.readline())
		(p, c) = ([0], [0])
		p.extend(list(map(int, stdin.readline().split())))
		c.extend(list(map(int, stdin.readline().split())))
		ans = 999999999
		already = [0] * (n + 1)
		for x in range(1, n + 1):
			if already[x] == 1:
				continue
			group = []
			y = x
			while already[y] == 0:
				already[y] = 1
				group.append(y)
				y = p[y]
			l = len(group)
			for step in range(1, l + 1):
				if ans <= step:
					break
				if l % step != 0:
					continue
				for z in range(0, step):
					is_ok = True
					pos = z
					while pos + step < l:
						if c[group[pos]] != c[group[pos + step]]:
							is_ok = False
							break
						pos += step
					if is_ok:
						ans = min(ans, step)
						break
		stdout.write(str(ans) + '\n')
main()


def get_divisors(N):
	res = []
	for i in range(1, N + 1):
		if i * i > N:
			break
		if N % i == 0:
			res.append(i)
			res.append(N // i)
	return res
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	N = int(input())
	P = [-9999999] + list(map(int, input().split()))
	C = [-9999999] + list(map(int, input().split()))
	Closed = [False] * (N + 1)
	ans = N
	for i in range(1, N + 1):
		if Closed[i]:
			continue
		Closed[i] = True
		p = i
		perm = [p]
		while True:
			p = P[p]
			if Closed[p]:
				break
			else:
				Closed[p] = True
				perm.append(p)
		l = len(perm)
		for d in get_divisors(l):
			if d >= ans:
				continue
			A = [True] * l
			for j in range(l):
				if not A[j - d] or C[perm[j]] != C[perm[j - d]]:
					A[j] = False
			if True in A[-d:]:
				ans = d
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	c = list(map(int, input().split()))
	shortest = n
	visited = [0] * n
	for j in range(n):
		if visited[j] == 0:
			l = 1
			visited[j] = 1
			x = j
			while visited[p[x] - 1] == 0:
				x = p[x] - 1
				visited[x] = 1
				l += 1
			x = j
			colors = [0] * l
			for k in range(l):
				colors[k] = c[x]
				x = p[x] - 1
			k = 1
			l2 = l
			while k ** 2 <= l:
				if l % k == 0:
					d = l // k
					works = 0
					for foo1 in range(k):
						if works == 0:
							col = colors[foo1]
							foo2 = foo1 + k
							works = 1
							while foo2 < l and works == 1:
								if colors[foo2] == col:
									foo2 += k
								else:
									works = 0
					if works == 1:
						l2 = min(l2, k)
					works = 0
					for foo1 in range(d):
						if works == 0:
							col = colors[foo1]
							foo2 = foo1 + d
							works = 1
							while foo2 < l and works == 1:
								if colors[foo2] == col:
									foo2 += d
								else:
									works = 0
					if works == 1:
						l2 = min(l2, d)
				k += 1
			shortest = min(shortest, l2)
	print(shortest)


def monocolor_subcycle(cycle, start, divisor, c):
	for i in range(start, len(cycle), divisor):
		v = cycle[i]
		if c[v] != c[cycle[start]]:
			return False
	return True

def any_monocolor_subcycle(cycle, divisor, c):
	for start in range(divisor):
		if monocolor_subcycle(cycle, start, divisor, c):
			return True
	return False

def min_in_cycle(cycle, c):
	length = len(cycle)
	local_ans = length
	divisor = 1
	while divisor * divisor <= length:
		if length % divisor == 0:
			if any_monocolor_subcycle(cycle, divisor, c):
				local_ans = min(local_ans, divisor)
				break
			if any_monocolor_subcycle(cycle, length // divisor, c):
				local_ans = min(local_ans, length // divisor)
		divisor += 1
	return local_ans

def find_cycle(v, used, p, cycle):
	used[v] = True
	cycle.append(v)
	while p[v] != cycle[0]:
		v = p[v]
		used[v] = True
		cycle.append(v)

def solution():
	n = int(input())
	p = [int(x) - 1 for x in input().split()]
	c = list(map(int, input().split()))
	ans = n
	used = [False] * n
	for v in range(n):
		if not used[v]:
			cycle = []
			find_cycle(v, used, p, cycle)
			ans = min(ans, min_in_cycle(cycle, c))
	all_ans.append(str(ans))
all_ans = []
t = int(input())
for _ in range(t):
	solution()
print('\n'.join(all_ans))


import os
import sys
if os.path.exists('/mnt/c/Users/Square/square/codeforces'):
	f = iter(open('D.txt').readlines())

	def input():
		return next(f).strip()
else:
	input = lambda : sys.stdin.readline().strip()
fprint = lambda *args: print(*args, flush=True)
import itertools
t = int(input())
from collections import Counter
for _ in range(t):
	n = int(input())
	p = [i - 1 for i in list(map(int, input().split()))]
	c = list(map(int, input().split()))
	arrs = []
	used = [0] * n
	for i in range(n):
		if not used[i]:
			cur = i
			tmp = []
			while not used[p[cur]]:
				cur = p[cur]
				tmp.append(c[cur])
				used[cur] = 1
			arrs.append(tmp)
	res = n
	for arr in arrs:
		larr = len(arr)
		for j in range(1, larr + 1):
			if larr % j != 0:
				continue
			for residue in range(j):
				if all([arr[t] == arr[residue] for t in range(residue, larr, j)]):
					res = min(res, j)
	print(res)


import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LI1():
	return list(map(int1, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():

	def factor(a):
		res = []
		for d in range(1, a + 1):
			if d ** 2 > a:
				break
			if a % d == 0:
				res.append(d)
				if d ** 2 != a:
					res.append(a // d)
		return res

	def solve(ans):
		for f in ff:
			if f >= ans:
				return ans
			for sj in range(f):
				pc = colors[sj]
				for j in range(sj + f, cn, f):
					c = colors[j]
					if c != pc:
						break
					pc = c
				else:
					return f
	q = II()
	for _ in range(q):
		n = II()
		pp = LI1()
		cc = LI()
		fin = [False] * n
		ans = 10 ** 9
		for i in range(n):
			if fin[i]:
				continue
			colors = []
			while not fin[i]:
				fin[i] = True
				colors.append(cc[i])
				i = pp[i]
			cn = len(colors)
			ff = factor(cn)
			ff.sort()
			ans = solve(ans)
		print(ans)
main()


for i in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	c = list(map(int, input().split()))
	p = [x - 1 for x in p]
	used = [0] * n
	ret = n
	for j in range(n):
		if used[j] == 0:
			cycle = []
			v = j
			while used[v] == 0:
				used[v] = 1
				cycle.append(v)
				v = p[v]
			l = len(cycle)
			for k in range(1, l + 1):
				if l % k == 0:
					for s in range(k):
						eq = True
						pos = s
						while pos + k < l:
							if c[cycle[pos]] != c[cycle[pos + k]]:
								eq = False
							pos += k
						if eq:
							ret = min(ret, k)
							break
	print(ret)


from itertools import combinations
from collections import Counter
MOD = 998244353

def divs(cnt):
	res = set()
	firstdiv = -1
	lastdiv = cnt
	for i in range(2, int(cnt ** 0.5 + 1)):
		if i > lastdiv:
			break
		if cnt % i == 0:
			res.add(i)
			res.add(cnt // i)
			if firstdiv == -1:
				firstdiv = i
				lastdiv = cnt // i
	return sorted(res)

def go():
	n = int(input())
	p = list(map(lambda x: int(x) - 1, input().split()))
	c = list(map(int, input().split()))
	done = [False] * n
	perms = {}
	colhist = {}
	colmax = {}
	for i in range(n):
		if not done[i]:
			colhist_i = Counter()
			done[i] = True
			colhist_i[c[i]] += 1
			j = p[i]
			cnt = 1
			while j != i:
				done[j] = True
				colhist_i[c[j]] += 1
				j = p[j]
				cnt += 1
			colhist[i] = colhist_i
			colmax[i] = max(colhist_i.values())
			perms[i] = cnt
			if len(colhist_i) == 1:
				return 1
	revperms = {}
	lim = n
	for (pp, cnt) in perms.items():
		revperms.setdefault(cnt, []).append(pp)
		lim = min(lim, cnt)
	for cnt in sorted(revperms.keys()):
		divisors = divs(cnt)
		for divisor in divisors:
			if divisor >= lim:
				break
			for perm in revperms[cnt]:
				if colmax[perm] < cnt // divisor:
					continue
				cols = [-1] * divisor
				i = perm
				for ind in range(divisor):
					cols[ind] = c[i]
					i = p[i]
				for ind in range(divisor, cnt):
					if c[i] != cols[ind % divisor]:
						cols[ind % divisor] = -1
					i = p[i]
				if any((col != -1 for col in cols)):
					lim = divisor
					break
	return lim
t = int(input())
ans = []
for _ in range(t):
	ans.append(str(go()))
print('\n'.join(ans))


import sys
input = lambda : sys.stdin.readline().rstrip()

def primeFactor(N):
	(i, n, ret, d, sq) = (2, N, {}, 2, 99)
	while i <= sq:
		k = 0
		while n % i == 0:
			(n, k, ret[i]) = (n // i, k + 1, k + 1)
		if k > 0 or i == 97:
			sq = int(n ** (1 / 2) + 0.5)
		if i < 4:
			i = i * 2 - 1
		else:
			(i, d) = (i + d, d ^ 6)
	if n > 1:
		ret[n] = 1
	return ret

def divisors(N):
	pf = primeFactor(N)
	ret = [1]
	for p in pf:
		ret_prev = ret
		ret = []
		for i in range(pf[p] + 1):
			for r in ret_prev:
				ret.append(r * p ** i)
	return sorted(ret)

def chk(X):
	n = len(X)
	XX = X * 2
	mi = 1 << 30
	for d in divisors(n):
		if d >= mi:
			break
		for i in range(d):
			for j in range(i, n + i, d):
				if XX[j] != XX[j + d]:
					break
			else:
				mi = min(mi, d)
	return mi
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(a) - 1 for a in input().split()]
	C = [int(a) - 1 for a in input().split()]
	done = [0] * N
	L = []
	for i in range(N):
		if done[i]:
			continue
		t = [C[i]]
		j = A[i]
		while j != i:
			t.append(C[j])
			done[j] = 1
			j = A[j]
		L.append(t)
	print(min([chk(a) for a in L]))


from sys import stdin
Pr = []
Cm = set()
for i in range(2, 450):
	if i in Cm:
		continue
	Pr.append(i)
	for j in range(i, 450, i):
		Cm.add(j)
seen = [False for _ in range(200000)]

def check(seq, f):
	ln = len(seq)
	for s in range(f):
		C = seq[s]
		for i in range(s, ln, f):
			if seq[i] != C:
				break
		else:
			return True

def solve(seq):
	if check(seq, 1):
		return 1
	ln = m = len(seq)
	done = set()
	for pr in Pr:
		if pr > m:
			break
		if ln % pr:
			continue
		for d in range(pr, ln + 1, pr):
			if ln % d:
				continue
			if d in done:
				continue
			done.add(d)
			if check(seq, d):
				m = min(m, d)
				break
			elif check(seq, ln // d):
				m = min(m, ln // d)
	return m
T = int(stdin.readline().strip())
ans = []
for _ in range(T):
	n = int(stdin.readline().strip())
	p = list(map(int, stdin.readline().split()))
	c = list(map(int, stdin.readline().split()))
	m = n
	for i in range(n):
		seen[i] = False
	for i in range(n):
		if seen[i]:
			continue
		(u, seq) = (i, [])
		while not seen[u]:
			seen[u] = True
			seq.append(c[u])
			u = p[u] - 1
		m = min(m, solve(seq))
		if m == 1:
			break
	ans.append(str(m))
print('\n'.join(ans))


def monocolor_subcycle(start, divisor):
	for i in range(start, len(cycle), divisor):
		v = cycle[i]
		if c[v] != c[cycle[start]]:
			return False
	return True

def any_monocolor_subcycle(divisor):
	for start in range(divisor):
		if monocolor_subcycle(start, divisor):
			return True
	return False

def min_in_cycle():
	length = len(cycle)
	local_ans = length
	divisor = 1
	while divisor * divisor <= length:
		if length % divisor == 0:
			if any_monocolor_subcycle(divisor):
				local_ans = min(local_ans, divisor)
				break
			if any_monocolor_subcycle(length // divisor):
				local_ans = min(local_ans, length // divisor)
		divisor += 1
	return local_ans

def find_cycle(v):
	global used, cycle
	used[v] = test
	cycle.append(v)
	while p[v] != cycle[0]:
		v = p[v]
		used[v] = test
		cycle.append(v)

def solution():
	global used, cycle
	ans = n
	for v in range(n):
		if used[v] != test:
			cycle = []
			find_cycle(v)
			ans = min(ans, min_in_cycle())
	answers.append(str(ans))
t = int(input())
used = [-1] * 2 * 10 ** 5
cycle = []
answers = []
for test in range(t):
	n = int(input())
	p = [int(x) - 1 for x in input().split()]
	c = list(map(int, input().split()))
	solution()
print('\n'.join(answers))


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from math import sqrt
t = int(input())
for tests in range(t):
	n = int(input())
	P = list(map(int, input().split()))
	C = list(map(int, input().split()))
	for i in range(n):
		P[i] -= 1
	USE = [0] * n
	ANS = n
	for i in range(n):
		if USE[i] == 1:
			continue
		cy = i
		CYCLE = []
		while USE[cy] != 1:
			USE[cy] = 1
			cy = P[cy]
			CYCLE.append(cy)
		LEN = len(CYCLE)
		x = LEN
		xr = int(sqrt(x)) + 1
		LIST = []
		for k in range(1, xr + 1):
			if x % k == 0:
				LIST.append(k)
				LIST.append(x // k)
		for l in LIST:
			if ANS <= LEN // l:
				continue
			COLORS = [-1] * (LEN // l)
			ind = 0
			for k in range(LEN):
				if COLORS[ind] == -1:
					COLORS[ind] = C[cy]
				elif COLORS[ind] == C[cy]:
					True
				else:
					COLORS[ind] = 0
				cy = P[cy]
				ind += 1
				if ind == LEN // l:
					ind = 0
			for c in COLORS:
				if c != 0:
					ANS = LEN // l
					break
	print(ANS)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import sys
print = sys.stdout.write

def divisors(a, ans):
	div = []
	t1 = int(a ** 0.5)
	for i in range(1, min(t1 + 1, ans)):
		if a % i == 0:
			div.append(i)
			div.append(int(a / i))
	div.sort()
	return div
for _ in range(int(input())):
	n = int(input())
	p = [int(i) - 1 for i in input().split()]
	c = list(map(int, input().split()))
	alive = [True] * n
	cycle = []
	ans = n
	for i in p:
		if alive[i]:
			cycle.append([])
			while True:
				if alive[i]:
					alive[i] = False
					cycle[-1].append(i)
					i = p[i]
				else:
					break
	for i in cycle:
		t2 = len(i)
		div = divisors(t2, ans)
		for j in div:
			if j >= ans:
				break
			for q in range(j):
				t4 = c[i[q]]
				for r in range(q + j, t2, j):
					if t4 != c[i[r]]:
						break
				else:
					ans = min(ans, j)
	print(str(ans) + '\n')


import sys

def bestval(pp, cc):
	k = len(pp)
	k_2 = k // 2 + 1
	for f in range(1, k_2):
		if k % f == 0:
			for offs in range(f):
				good = True
				num = cc[offs]
				upp = k // f // 2 + 1
				for j in range(1, upp):
					v1 = f * j
					v2 = k - v1 + offs
					v1 += offs
					if cc[v1] != num or cc[v2] != num:
						good = False
						break
				if good:
					return f
	return k
for q in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	p = [int(j) - 1 for j in sys.stdin.readline().split()]
	c = [int(j) - 1 for j in sys.stdin.readline().split()]
	fnd = [0] * n
	ans = n + 1
	for i in range(n):
		if not fnd[i]:
			ppp = [i]
			ccc = [c[i]]
			fnd[i] = 1
			j = p[i]
			while j != i:
				fnd[j] = 1
				ppp.append(j)
				ccc.append(c[j])
				j = p[j]
			ans = min(ans, bestval(ppp, ccc))
	sys.stdout.write(str(ans) + '\n')


import sys
input = sys.stdin.readline
input_list = lambda : list(map(int, input().split()))

def factorize(n):
	a = []
	i = 1
	while i * i <= n:
		if n % i == 0:
			a.append(i)
			if i * i != n:
				a.append(n // i)
		i += 1
	return a

def main():
	t = int(input())
	while t > 0:
		t -= 1
		n = int(input())
		p = input_list()
		c = input_list()
		ans = len(p)
		used = [False] * (len(p) + 1)
		length = len(p)
		for i in range(length):
			if used[i]:
				continue
			used[i] = True
			j = p[i] - 1
			temp = [j]
			while j != i:
				j = p[j] - 1
				used[j] = True
				temp.append(j)
			t_len = len(temp)
			factors = factorize(t_len)
			ans = min(ans, t_len)
			for k in factors:
				for l in range(k):
					index = (l + k) % t_len
					while index != l and c[temp[(index - k + t_len) % t_len]] == c[temp[index]]:
						index = (index + k) % t_len
					if index == l:
						ans = min(ans, k)
		print(ans)

def exp(a, n):
	if n == 0:
		return 1
	result = a
	residue = 1
	while n > 1:
		if n % 2 == 1:
			residue = residue * result % MOD
		result = result * result % MOD
	return result * residue % MOD
main()


import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines
int1 = lambda x: int(x) - 1
ns = lambda : readline().rstrip()
ni = lambda : int(readline().rstrip())
nm = lambda : map(int, readline().split())
nl = lambda : list(map(int1, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
	n = ni()
	p = nl()
	c = nl()
	ans = n
	use = [0] * n
	for i in range(n):
		if use[i]:
			continue
		v = i
		cc = [c[v]]
		use[v] = 1
		while not use[p[v]]:
			v = p[v]
			cc.append(c[v])
			use[v] = 1
		m = len(cc)
		ans = min(ans, m)
		flag = 0
		for j in range(1, min(m // 2 + 1, ans)):
			if m % j:
				continue
			ok = [True] * m
			for k in range(j):
				if len(set(cc[k::j])) == 1:
					ans = min(ans, j)
					flag = 1
					break
			if flag:
				break
	print(ans)
	return
T = ni()
for _ in range(T):
	solve()


from sys import stdin, gettrace
if not gettrace():

	def input():
		return next(stdin)[:-1]

def main():

	def solve():
		n = int(input())
		pp = [int(a) - 1 for a in input().split()]
		cc = [int(a) for a in input().split()]
		in_cycle = [False] * n
		cycles = []
		next_cycle = 0
		while next_cycle < n:
			cycles.append([next_cycle])
			in_cycle[next_cycle] = True
			cur = next_cycle
			while pp[cur] != next_cycle:
				cur = pp[cur]
				cycles[-1].append(cur)
				in_cycle[cur] = True
			while next_cycle < n and in_cycle[next_cycle]:
				next_cycle += 1
		best = n
		for cycle in cycles:
			l = len(cycle)
			i = 1
			div = []
			div2 = []
			while i * i <= l and i < best:
				if l % i == 0:
					div.append(i)
					div2.append(l // i)
				i += 1
			div += div2[::-1]
			for i in div:
				if i >= best:
					break
				for j in range(i):
					c = cc[cycle[j]]
					for k in cycle[i + j::i]:
						if cc[k] != c:
							break
					else:
						best = i
						break
		print(best)
	q = int(input())
	for _ in range(q):
		solve()
main()


import sys
input = sys.stdin.readline

def divisors(n, min_pow):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			if i < min_pow:
				divisors.append(i)
			if i != n // i and n // i < min_pow:
				divisors.append(n // i)
	divisors.sort()
	return divisors
t = int(input())
for _ in range(t):
	n = int(input())
	p = [int(item) - 1 for item in input().split()]
	c = [int(item) for item in input().split()]
	cycles = []
	visited = [0] * n
	for item in p:
		if visited[item]:
			continue
		curr = item
		cycle = []
		while not visited[curr]:
			cycle.append(c[curr])
			visited[curr] = 1
			curr = p[curr]
		cycles.append(cycle)
	min_pow = n
	for cycle in cycles:
		min_pow = min(min_pow, len(cycle))
	for cycle in cycles:
		div = divisors(len(cycle), min_pow)
		for d in div:
			for start in range(d):
				color = cycle[start]
				ok = True
				for item in cycle[start::d]:
					if item != color:
						ok = False
						break
				if ok:
					break
			if ok:
				min_pow = min(min_pow, d)
	print(min_pow)


import io
import os
from math import gcd
from collections import Counter, defaultdict, deque

def solve(N, P, C):
	assert len(P) == N
	assert len(C) == N
	seen = set()
	best = float('inf')
	for i in range(N):
		if i not in seen:
			temp = i
			seen.add(temp)
			cycle = [C[temp]]
			while P[temp] not in seen:
				temp = P[temp]
				seen.add(temp)
				cycle.append(C[temp])
			cycleLen = len(cycle)
			if len(set(cycle)) == 1:
				return 1
			best = min(best, cycleLen)
			gcdSeen = {1}
			for k in range(2, cycleLen):
				kWorks = False
				g = gcd(k, cycleLen)
				if g in gcdSeen:
					continue
				gcdSeen.add(g)
				for off in range(g):
					colors = [cycle[index] for index in range(off, cycleLen, k)]
					if False:
						print('trying', 'k', k, 'off', off, [index for index in range(off, cycleLen, k)], colors)
					assert len(colors) == cycleLen // g
					if len(set(colors)) == 1:
						kWorks = True
						break
				if kWorks:
					best = min(best, k)
					break
	return best
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input())
for t in range(T):
	(N,) = [int(x) for x in input().split()]
	P = [int(x) - 1 for x in input().split()]
	C = [int(x) - 1 for x in input().split()]
	ans = solve(N, P, C)
	print(ans)


from sys import stdin
input = stdin.readline
q = int(input())
for rwerew in range(q):
	n = int(input())
	p = list(map(int, input().split()))
	c = list(map(int, input().split()))
	for i in range(n):
		p[i] -= 1
	przyn = [0] * n
	grupa = []
	i = 0
	while i < n:
		if przyn[i] == 1:
			i += 1
		else:
			nowa_grupa = [i]
			j = p[i]
			przyn[i] = 1
			while j != i:
				przyn[j] = 1
				nowa_grupa.append(j)
				j = p[j]
			grupa.append(nowa_grupa)
	grupacol = []
	for i in grupa:
		cyk = []
		for j in i:
			cyk.append(c[j])
		grupacol.append(cyk)
	mini = 234283742834
	for cykl in grupacol:
		dziel = []
		d = 1
		while d ** 2 <= len(cykl):
			if len(cykl) % d == 0:
				dziel.append(d)
			d += 1
		dodat = []
		for d in dziel:
			dodat.append(len(cykl) / d)
		dziel_ost = list(map(int, dziel + dodat))
		for dzielnik in dziel_ost:
			for i in range(dzielnik):
				indeks = i
				secik = set()
				chuj = True
				while indeks < len(cykl):
					secik.add(cykl[indeks])
					indeks += dzielnik
					if len(secik) > 1:
						chuj = False
						break
				if chuj:
					mini = min(mini, dzielnik)
	print(mini)


T = int(input())
for _ in range(T):
	n = int(input())
	perm = list([int(x) - 1 for x in input().split()])
	color = list(map(int, input().split()))
	SMALL = n
	unseen = set(range(n))
	while unseen:
		start = unseen.pop()
		l = [start]
		nex = start
		while perm[nex] != start:
			nex = perm[nex]
			l.append(nex)
			unseen.remove(nex)
		size = len(l)
		factors = []
		curr = 1
		while curr * curr <= size:
			if size % curr == 0:
				factors.append(curr)
				factors.append(size // curr)
			curr += 1
		for f in factors:
			works = [True] * f
			for i in range(size):
				if color[l[i]] != color[l[i % f]]:
					works[i % f] = False
			for b in works:
				if b:
					SMALL = min(SMALL, f)
					break
	print(SMALL)


import sys
input = sys.stdin.readline
print = sys.stdout.write
MAX = 2 * 10 ** 5 + 1

def divisors(a, ans):
	div = []
	t1 = int(a ** 0.5)
	for i in range(1, min(t1 + 1, ans)):
		if a % i == 0:
			div.append(i)
			div.append(int(a / i))
	div.sort()
	return div
for ti in range(int(input())):
	n = int(input())
	p = [int(x) - 1 for x in input().split()]
	c = [int(x) for x in input().split()]
	ans = float('inf')
	visited = [0] * n
	for i in range(n):
		m = 0
		cycle = []
		cn = i
		while not visited[cn]:
			visited[cn] = 1
			cycle.append(c[cn])
			cn = p[cn]
			m += 1
		for fi in divisors(m, ans):
			for fj in range(fi):
				valid = True
				for ci in range(fj, m, fi):
					valid &= cycle[ci] == cycle[fj]
				if valid:
					ans = min(ans, fi)
	print(str(ans))
	print('\n')


import sys
T = int(sys.stdin.readline().strip())
Q = []
P = [0] * 10 ** 6
for i in range(2, 2 * 10 ** 5 + 10):
	v = True
	if P[i] == 0:
		Q.append(i)
		j = i
		while j < 10 ** 6:
			P[j] = 1
			j = j + i

def factors(n):
	i2 = 0
	ans = [1]
	while n > 1:
		m = 0
		while n % Q[i2] == 0:
			m = m + 1
			n = n // Q[i2]
		ans2 = []
		for h in range(0, m + 1):
			for j in ans:
				ans2.append(j * Q[i2] ** h)
		i2 = i2 + 1
		ans = ans2[:]
	return ans
for t in range(0, T):
	n = int(sys.stdin.readline())
	p = list(map(int, sys.stdin.readline().strip().split()))
	c = list(map(int, sys.stdin.readline().strip().split()))
	for i in range(0, n):
		p[i] = p[i] - 1
	P = []
	L = []
	i = 0
	ans = n
	while i < n:
		if p[i] == -1:
			i = i + 1
		else:
			j = i
			x = [j]
			while p[j] != i:
				x.append(p[j])
				j2 = p[j]
				p[j] = -1
				j = j2
			p[j] = -1
			P.append(x)
			l = len(x)
			F = factors(l)
			for f in F:
				for j in range(0, f):
					v = True
					for h in range(0, l // f):
						if c[x[j + h * f]] != c[x[j]]:
							v = False
					if v == True:
						ans = min(ans, f)
	print(ans)


import sys
input = sys.stdin.readline

def divisors(n):
	divisors = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			divisors.append(i)
			if i != n // i:
				divisors.append(n // i)
	divisors.sort()
	return divisors

def check(p):
	m = len(p)
	for k in divisors(m):
		for i in range(k):
			ty = None
			for j in range(m // k):
				y = Y[p[i + j * k] - 1]
				if ty == None:
					ty = y
				elif y != ty:
					break
			else:
				return k
(t,) = map(int, input().split())
for _ in range(t):
	n = int(input())
	X = list(map(int, input().split()))
	Y = list(map(int, input().split()))
	vs = set()
	ps = []
	for i in range(1, n + 1):
		if i in vs:
			continue
		vs.add(i)
		stack = [i]
		path = [i]
		while stack:
			v = stack.pop()
			u = X[v - 1]
			if u in vs:
				continue
			path.append(u)
			vs.add(u)
			stack.append(u)
		ps.append(path)
	m = n
	for p in ps:
		m = min(m, check(p))
	print(m)


for tc in range(int(input())):
	n = int(input())
	perm = list(map(int, input().split()))
	colors = list(map(int, input().split()))
	lss = []
	vis = set()
	for i in range(n):
		if i in vis:
			continue
		ls = [i]
		pos = i
		vis.add(i)
		while perm[pos] - 1 != ls[0]:
			pos = perm[pos] - 1
			vis.add(pos)
			ls.append(pos)
		lss.append(ls)
	best = 100000000
	for ls in lss:
		for period in range(1, len(ls) + 1):
			if len(ls) % period:
				continue
			for beg in range(period):
				for e in range(beg, len(ls), period):
					if colors[ls[e]] != colors[ls[beg]]:
						break
				else:
					best = min(best, period)
	print(best)


def uoc(x):
	i = 1
	arr = []
	while i * i <= x:
		if x % i == 0:
			arr.append(i)
			if i * i != x:
				arr.append(x // i)
		i += 1
	return sorted(arr)

def is_ok(arr, n, u):
	for i in range(u):
		cur = i
		flg = True
		for j in range(n // u):
			if arr[cur] != arr[(cur + u) % n]:
				flg = False
				break
			cur += u
		if flg == True:
			return True
	return False

def min_period(arr):
	n = len(arr)
	u_arr = uoc(n)
	for u in u_arr:
		if is_ok(arr, n, u):
			return u
for _ in range(int(input())):
	n = int(input())
	p = [-1] + list(map(int, input().split()))
	c = [-1] + list(map(int, input().split()))
	used = [0] * (n + 1)
	ans = float('inf')
	for x in range(1, n + 1):
		if used[x] == 0:
			arr = [c[x]]
			used[x] = 1
			while used[p[x]] == 0:
				x = p[x]
				used[x] = 1
				arr.append(c[x])
			ans = min(ans, min_period(arr))
	print(ans)


answers = []
for _ in range(int(input())):
	n = int(input())
	P = [0] + list(map(int, input().split()))
	C = [0] + list(map(int, input().split()))
	ccl = []
	used = [0] * (n + 1)
	for v in range(1, n + 1):
		if used[v] == 0:
			used[v] = 1
			x = P[v]
			kk = [C[v]]
			while used[x] == 0:
				kk.append(C[x])
				used[x] = 1
				x = P[x]
			ccl.append(kk)
	ans = n
	for i in range(1, n + 1):
		if i == P[i]:
			ans = 1
	for p in ccl:
		g = len(p)
		for h in range(1, int(g ** 0.5) + 1):
			if g % h == 0:
				hh = g // h
				for Q in [h, hh]:
					can = 0
					for st in range(Q):
						color = p[st]
						cac = 1
						for z in range(1, g // Q):
							if p[st + Q * z] != color:
								cac = 0
								break
						if cac == 1:
							can = 1
							break
					if can:
						ans = min(ans, Q)
	answers.append(ans)
print('\n'.join(list(map(str, answers))))