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: interview

Starter code:

Solutions:
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)

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: list(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)



# Made By Mostafa_Khaled


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

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 = [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)