Pavel cooks barbecue. There are n skewers, they lay on a brazier in a row, each on one of n positions. Pavel wants each skewer to be cooked some time in every of n positions in two directions: in the one it was directed originally and in the reversed direction.

Pavel has a plan: a permutation p and a sequence b_1, b_2, ..., b_{n}, consisting of zeros and ones. Each second Pavel move skewer on position i to position p_{i}, and if b_{i} equals 1 then he reverses it. So he hope that every skewer will visit every position in both directions.

Unfortunately, not every pair of permutation p and sequence b suits Pavel. What is the minimum total number of elements in the given permutation p and the given sequence b he needs to change so that every skewer will visit each of 2n placements? Note that after changing the permutation should remain a permutation as well.

There is no problem for Pavel, if some skewer visits some of the placements several times before he ends to cook. In other words, a permutation p and a sequence b suit him if there is an integer k (k ≥ 2n), so that after k seconds each skewer visits each of the 2n placements.

It can be shown that some suitable pair of permutation p and sequence b exists for any n.


-----Input-----

The first line contain the integer n (1 ≤ n ≤ 2·10^5) — the number of skewers.

The second line contains a sequence of integers p_1, p_2, ..., p_{n} (1 ≤ p_{i} ≤ n) — the permutation, according to which Pavel wants to move the skewers.

The third line contains a sequence b_1, b_2, ..., b_{n} consisting of zeros and ones, according to which Pavel wants to reverse the skewers.


-----Output-----

Print single integer — the minimum total number of elements in the given permutation p and the given sequence b he needs to change so that every skewer will visit each of 2n placements.


-----Examples-----
Input
4
4 3 2 1
0 1 1 1

Output
2

Input
3
2 3 1
0 0 0

Output
1



-----Note-----

In the first example Pavel can change the permutation to 4, 3, 1, 2.

In the second example Pavel can change any element of b to 1.

Difficulty: MEDIUM_HARD
Tags: Graph traversal

Constructive algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
n = int(input())
permutation = list(map(int, input().split()))
go = set(range(1, n + 1))
reached = set()
ans = 0
while go:
	x = go.pop()
	while x not in reached:
		reached.add(x)
		x = permutation[x - 1]
		if x in go:
			go.remove(x)
	ans += 1
if ans == 1:
	ans = 0
permutation = input().split()
if permutation.count('1') % 2 == 0:
	ans += 1
print(ans)


n = int(input())
p = list(map(int, input().split()))
b = list(map(int, input().split()))
s = sum((b[i] for i in range(n)))
if s % 2 == 0:
	ans = 1
else:
	ans = 0
visited = [0] * n
ptr = 0
start = 1
visited[0] = 1
q = 1
c = 1
while q < n:
	start = p[start - 1]
	if visited[start - 1] == 1:
		c += 1
		while ptr < n and visited[ptr] == 1:
			ptr += 1
		start = ptr + 1
	else:
		visited[start - 1] = 1
		q += 1
if c == 1:
	print(ans)
else:
	print(ans + c)


n = int(input())
p = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
ans = 0
visited = [False for i in range(n)]
for i in range(n):
	if visited[i]:
		continue
	ans += 1
	while not visited[i]:
		visited[i] = True
		i = p[i] - 1
if ans == 1:
	ans = 0
ans += (sum(b) + 1) % 2
print(ans)


read = lambda : map(int, input().split())
n = int(input())
p = list(read())
b = list(read())
ans = (b.count(1) + 1) % 2
was = [0] * n
cnt = 0
for i in range(n):
	if not was[i]:
		cnt += 1
		v = i
		while not was[v]:
			was[v] = 1
			v = p[v] - 1
if cnt > 1:
	ans += cnt
print(ans)


amount = int(input())
movement = list(map(int, input().split()))
reachable = [False] * amount
flip = sum(list(map(int, input().split())))
changesneeded = 0
flipneeded = 0
if flip % 2 == 0:
	flipneeded = 1
for i in range(amount):
	if not reachable[i]:
		changesneeded += 1
		point = i
		while True:
			if reachable[point]:
				break
			reachable[point] = True
			point = movement[point] - 1
if changesneeded > 1:
	print(changesneeded + flipneeded)
else:
	print(flipneeded)


n = int(input())
p = [int(i) for i in input().split()]
zeros = [int(i) for i in input().split()]
ans = 0
if not sum(zeros) % 2:
	ans += 1
visited = [False for i in range(n)]
ciclos = 0
for i in range(n):
	if not visited[i]:
		ciclos += 1
	j = i
	while not visited[j]:
		visited[j] = True
		j = p[j] - 1
if ciclos == 1:
	ans += 0
else:
	ans += ciclos
print(ans)


n = int(input())
perm = list(map(int, input().split()))
zeros = list(map(int, input().split()))
answer = 0
if sum(zeros) % 2 == 0:
	answer += 1
visited = [False] * n
cycles = 0
for i in range(n):
	if not visited[i]:
		cycles += 1
	j = i
	while not visited[j]:
		visited[j] = True
		j = perm[j] - 1
answer += 0 if cycles == 1 else cycles
print(answer)


import sys

def main():
	n = int(sys.stdin.readline())
	p = list(map(int, sys.stdin.readline().split()))
	b = list(map(int, sys.stdin.readline().split()))
	for i in range(n):
		p[i] = p[i] - 1
	cur = 0
	res = 0
	while cur < n:
		if p[cur] == -1:
			cur += 1
			continue
		v = p[cur]
		cc = cur
		while v != -1:
			p[cc] = -1
			cc = v
			v = p[cc]
		res += 1
		cur += 1
	if res == 1:
		res = 0
	if sum(b) % 2 == 0:
		res += 1
	print(res)
main()


n = int(input())
p = list(map(int, input().split()))
b = list(map(int, input().split()))
visited = [False] * n
loops = 0
for i in range(n):
	if visited[i]:
		continue
	loops += 1
	while not visited[i]:
		visited[i] = True
		i = p[i] - 1
dp = 0 if loops == 1 else loops
db = (sum(b) + 1) % 2
print(dp + db)


import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
p = list(map(int, input().split()))
b = list(map(int, input().split()))
used = [False] * n
comp = 0
for i in range(n):
	if not used[i]:
		u = i
		while True:
			used[u] = True
			v = p[u] - 1
			if not used[v]:
				u = v
			else:
				break
		comp += 1
if comp == 1:
	ans = 0
else:
	ans = comp
ed = 0
for i in range(n):
	if b[i]:
		ed += 1
if not ed % 2:
	ans += 1
print(ans)


(n,) = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
swaps = sum(map(int, input().split()))
res = 1 - swaps % 2
visited = [False for _ in range(n)]
cycles = 0
for i in range(n):
	if visited[i]:
		continue
	visited[i] = True
	j = p[i]
	while j != i:
		visited[j] = True
		j = p[j]
	cycles += 1
if cycles > 1:
	res += cycles
print(res)


n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
sums1 = 0
for j in range(n):
	if B[j] == 1:
		sums1 += 1
if sums1 % 2 == 0:
	ans = 1
visited = [0] * n
cou = 0
for j in range(n):
	if visited[j] == 0:
		visited[j] = 1
		while True:
			if visited[A[j] - 1] == 0:
				visited[A[j] - 1] = 1
				j = A[j] - 1
			else:
				cou += 1
				break
if cou != 1:
	ans += cou
print(ans)


n = int(input())
p = list(map(int, input().split()))
b = list(map(int, input().split()))
cnt_cyc = 0
vis = [0] * n
for i in range(n):
	if vis[i] == 0:
		vis[i] = 1
		nxt = p[i] - 1
		while vis[nxt] == 0:
			vis[nxt] = 1
			nxt = p[nxt] - 1
		cnt_cyc += 1
res = (b.count(1) + 1) % 2
print(res if cnt_cyc == 1 else res + cnt_cyc)


class Graph:

	def __init__(self, n):
		self.nodes = n
		self.edge_mapping = []
		for x in range(self.nodes + 1):
			self.edge_mapping.append([])

	def add_edge(self, src, dest):
		if self.edge_mapping[src] == None:
			self.edge_mapping[src] = [dest]
		else:
			self.edge_mapping[src].append(dest)

	def dfs_inner(self, nd, mark_list):
		stack = []
		stack.append(nd)
		while len(stack) != 0:
			node = stack.pop()
			mark_list[node] = 1
			for n in self.edge_mapping[node]:
				if mark_list[n] == 0:
					stack.append(n)

	def dfs(self):
		mark_list = [0] * (self.nodes + 1)
		ret = 0
		for i in range(1, self.nodes + 1):
			if mark_list[i] != 1:
				self.dfs_inner(i, mark_list)
				ret += 1
		return ret

	def printg(self):
		for z in self.edge_mapping:
			print(z)
n = int(input())
g = Graph(n)
p_list = list(map(int, input().split()))
s_list = list(map(int, input().split()))
for x in range(len(p_list)):
	g.add_edge(p_list[x], x + 1)
ans = 0
trav = g.dfs()
if trav != 1:
	ans += trav
s = 0
for x in s_list:
	s += x
if s % 2 == 0:
	print(ans + 1)
else:
	print(ans)


def dfs(x):
	if vis[p[x]] == False:
		vis[p[x]] = True
		dfs(p[x])
n = int(input())
p = list(map(int, input().split()))
b = list(map(int, input().split()))
vis = [False] * n
num = 0
for i in range(0, n):
	p[i] = p[i] - 1
for i in range(0, n):
	if vis[i] == False:
		while vis[i] == False:
			vis[i] = True
			i = p[i]
		num = num + 1
if num != 1:
	ans = num
else:
	ans = 0
num = 0
for bx in b:
	if bx == 1:
		num = num + 1
if num % 2 == 0:
	ans = ans + 1
print(ans)


import sys
n = int(input())
p = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
ans = 0
num_cycles = 0
checked = set()
for i in range(n):
	if i in checked:
		continue
	checked.add(i)
	nxt = p[i] - 1
	while nxt != i:
		checked.add(nxt)
		nxt = p[nxt] - 1
	num_cycles += 1
ans += num_cycles if num_cycles != 1 else 0
ans += sum(b) % 2 == 0
print(ans)


import sys
input = sys.stdin.readline
N = int(input())
permu = list(map(int, input().split()))
permu = [i - 1 for i in permu]
blist = list(map(int, input().split()))
cyclefind = [False for i in range(N)]
cyclenum = 0
for i in range(N):
	if cyclefind[i] == False:
		cyclenum += 1
		q = i
		while cyclefind[q] != True:
			cyclefind[q] = True
			q = permu[q]
if cyclenum == 1:
	cyclenum = 0
if blist.count(1) % 2 == 0:
	cyclenum += 1
print(cyclenum)


from sys import stdin, stdout

def rint():
	return map(int, stdin.readline().split())
n = int(input())
p = list(rint())
b = list(rint())
p = [i - 1 for i in p]
v = [0] * n
loop = 0
for i in range(n):
	if v[i]:
		continue
	loop += 1
	while v[i] == 0:
		v[i] = 1
		i = p[i]
ans = 0
if loop != 1:
	ans += loop
if sum(b) % 2 == 0:
	ans += 1
print(ans)


import sys
input = sys.stdin.readline

class Unionfind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [1] * n

	def root(self, x):
		p = x
		while not self.par[p] < 0:
			p = self.par[p]
		while x != p:
			tmp = x
			x = self.par[x]
			self.par[tmp] = p
		return p

	def unite(self, x, y):
		(rx, ry) = (self.root(x), self.root(y))
		if rx == ry:
			return False
		if self.rank[rx] < self.rank[ry]:
			(rx, ry) = (ry, rx)
		self.par[rx] += self.par[ry]
		self.par[ry] = rx
		if self.rank[rx] == self.rank[ry]:
			self.rank[rx] += 1

	def is_same(self, x, y):
		return self.root(x) == self.root(y)

	def count(self, x):
		return -self.par[self.root(x)]
n = int(input())
p = list(map(int, input().split()))
b = list(map(int, input().split()))
uf = Unionfind(n)
for i in range(n):
	uf.unite(i, p[i] - 1)
rs = set((uf.root(i) for i in range(n)))
if len(rs) == 1:
	ans = 0
else:
	ans = len(rs)
if b.count(1) % 2 == 0:
	ans += 1
print(ans)


n = int(input())
p = list(map(int, input().split()))
b = list(map(int, input().split()))
count_cycles = 0
visited = [False] * n
for i in range(n):
	if not visited[i]:
		visited[i] = True
		nxt = p[i] - 1
		while not visited[nxt]:
			visited[nxt] = True
			nxt = p[nxt] - 1
		count_cycles += 1
if count_cycles == 1:
	print((b.count(1) + 1) % 2)
else:
	print(count_cycles + (b.count(1) + 1) % 2)


from collections import deque

def read(type=int):
	return type(input())

def read_arr(type=int):
	return [type(token) for token in input().split()]

def num_cycles(P):
	V = [False] * len(P)
	i = 0
	for u in P:
		if not V[u]:
			while not V[u]:
				V[u] = True
				u = P[u]
			i += 1
	return i

def runB():
	n = read()
	P = read_arr()
	P = [a - 1 for a in P]
	B = read_arr()
	extra = (sum(B) + 1) % 2
	cycles = num_cycles(P)
	ans = extra + (cycles if cycles > 1 else 0)
	print(ans)
runB()


from sys import stdin, stdout
n = int(stdin.readline())
numbers = list(map(int, stdin.readline().split()))
mask = list(map(int, stdin.readline().split()))
visit = [0 for i in range(n + 1)]
value = 1
for i in range(1, n + 1):
	if not visit[i]:
		u = i
		while not visit[u]:
			visit[u] = value
			u = numbers[u - 1]
		value += 1
if max(visit) == 1:
	ans = (sum(mask) + 1) % 2
else:
	ans = (sum(mask) + 1) % 2 + max(visit)
stdout.write(str(ans))


n = int(input())
p = [[0, 1] for i in range(n)]
b = [0 for i in range(n)]
ans = 0
s = input().split()
for i in range(n):
	p[i][0] = int(s[i]) - 1
s = input().split()
for i in range(n):
	b[i] = int(s[i])
temp = 0
cyc = 0
for i in range(n):
	if p[i][1] == 0:
		continue
	cyc += 1
	temp = i
	while p[temp][1] == 1:
		p[temp][1] = 0
		temp = p[temp][0]
if cyc > 1:
	ans = cyc
if sum(b) % 2 == 0:
	ans += 1
print(str(ans))


n = int(input())
p = map(int, input().split())
p = [x - 1 for x in p]
b = map(int, input().split())
s = int(sum(b))
c = 0
done = set()
for i in range(n):
	if i not in done:
		c += 1
		j = i
		while j not in done:
			done.add(j)
			j = p[j]
modif = 0
if c > 1:
	modif = c
res = modif + (s + 1) % 2
print(res)


n = int(input())
p = list(map(lambda x: int(x) - 1, input().split()))
b = list(map(int, input().split()))
cp = 0
z = [True] * n
old = -1
nn = n
while nn:
	cp += 1
	cur = next((i for i in range(old + 1, n) if z[i]))
	old = cur
	while z[cur]:
		z[cur] = False
		nn -= 1
		cur = p[cur]
if cp == 1:
	cp = 0
cb = 1 - (sum(b) & 1)
print(cb + cp)


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
k = 0
s = 0
v = [False] * n
for i in range(n):
	if v[i]:
		continue
	k += 1
	while not v[i]:
		v[i] = True
		i = a[i] - 1
if k == 1:
	k = 0
else:
	s += k
if sum(b) % 2 == 0:
	s += 1
print(s)