Pavel and barbecue

题意翻译

【题目描述】 Pavel 在烤肉。 共有 $n$ 串烤肉排成一排，各自在 $n$ 个位置中的一个。Pavel 希望每一串烤肉的每一面都能在每一个位置上烤过一次。 Pavel 有一个全排列 $p$ 和一个长为 $n$ 的 0/1 序列 $b$。Pavel 每一步将位于 $i$ 的串串移到 $p_i$ 处。同时，如果 $b_i=1$，那么 Pavel 将反转这个串串。 很不幸，不是每一对 $p$ 和 $b$ 都满足要求，Pavel 想知道最少修改多少个现有的 $p$ 和 $b$ 中的数才能满足自己的目的。注意修改后的序列也要满足要求。 易证这样的 $p$ 和 $b$ 对于所有的 $n$ 都是存在的。 【输入格式】 第一行一个正整数 $n$，烤串的数量。 第二行 $n$ 个正整数，分别表示 $p_1,p_2,\cdots,p_n$。 第三行 $n$ 个正整数，分别表示 $b_1,b_2,\cdots,b_n$。 【输出格式】 一行一个正整数，表示最小的操作次数。 【数据规模与约定】 $1\le p_i\le n\le 2\times 10^5$，$b_i\in \{0,1\}$

题目描述

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 $ .

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

4
4 3 2 1
0 1 1 1

输出样例 #1

2

输入样例 #2

3
2 3 1
0 0 0

输出样例 #2

1

说明

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 $ .

题意翻译

【题目描述】 Pavel 在烤肉。 共有 $n$ 串烤肉排成一排，各自在 $n$ 个位置中的一个。Pavel 希望每一串烤肉的每一面都能在每一个位置上烤过一次。 Pavel 有一个全排列 $p$ 和一个长为 $n$ 的 0/1 序列 $b$。Pavel 每一步将位于 $i$ 的串串移到 $p_i$ 处。同时，如果 $b_i=1$，那么 Pavel 将反转这个串串。 很不幸，不是每一对 $p$ 和 $b$ 都满足要求，Pavel 想知道最少修改多少个现有的 $p$ 和 $b$ 中的数才能满足自己的目的。注意修改后的序列也要满足要求。 易证这样的 $p$ 和 $b$ 对于所有的 $n$ 都是存在的。 【输入格式】 第一行一个正整数 $n$，烤串的数量。 第二行 $n$ 个正整数，分别表示 $p_1,p_2,\cdots,p_n$。 第三行 $n$ 个正整数，分别表示 $b_1,b_2,\cdots,b_n$。 【输出格式】 一行一个正整数，表示最小的操作次数。 【数据规模与约定】 $1\le p_i\le n\le 2\times 10^5$，$b_i\in \{0,1\}$