← 返回题目列表

Codeforces · 756/A

A. 帕维尔和烧烤

中文机器翻译题面 查看原题

帕维尔做饭烧烤。有n根串,它们排成一排放在火盆上,每个串在n个位置上。 Pavel 希望每个串在两个方向上的 n 个位置中的每一个上烹饪一段时间:在原来的方向上和相反的方向上。

Pavel 有一个计划:一个排列 p 和一个由 0 和 1 组成的序列 b1, b2, ..., bn。每隔一秒,帕维尔都会将位置 i 上的串移到位置 pi,如果 bi 等于 1,则将其反转。所以他希望每一个串都双向访问每一个位置。

不幸的是,并不是每一对排列 p 和序列 b 都适合 Pavel。在给定的排列 p 和给定的序列 b 中,他需要改变的最小元素总数是多少,以便每个串都会访问 2n 个位置中的每一个?请注意,更改排列后也应保持排列不变。

对于帕维尔来说,如果某个串烧在他结束烹饪之前多次访问某些位置,那没有问题。换句话说,如果存在整数 k (k ≥ 2n),则排列 p 和序列 b 适合他,因此在 k 秒后,每个串都会访问 2n 个位置中的每一个。

可以证明对于任何n 都存在一些合适的排列p 和序列b 对。

输入

第一行包含整数 n (1 ≤ n ≤ 2·105) — 串的数量。

第二行包含整数序列 p1, p2, ..., pn (1 ≤ pi ≤ n) — 排列,Pavel 想要根据该排列移动串。

第三行包含由 0 和 1 组成的序列 b1, b2, ..., bn,Pavel 想要根据该序列反转串。

输出

打印单个整数 - 给定排列 p 和给定序列 b 中元素的最小总数,他需要更改,以便每个串都会访问 2n 个位置中的每一个。

示例

输入 #1

4
4 3 2 1
0 1 1 1

输出 #1

2

输入 #2

3
2 3 1
0 0 0

输出 #2

1

注意

在第一个示例中,Pavel 可以将排列更改为 4, 3, 1, 2。

在第二个示例中,Pavel 可以将 b 的任何元素更改为 1。