← 返回题目列表

AtCoder · agc038_f

F. 两种排列

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

分数: 1600 点

问题陈述

Snuke 有排列 (P_0,P_1,\cdots,P_{N-1}) 和 (Q_0,Q_1,\cdots,Q_{N-1}) of (0,1,\cdots,N-1).

现在,他将进行新的排列 A 和 B of (0,1,\cdots,N-1),在以下条件下:

  • 对于每个 i (0 \leq i \leq N-1), A_i 应该是 i or P_i.
  • 对于每个 i (0 \leq i \leq N-1), B_i 应该是 i or Q_i.

让我们定义排列的距离 A 和 B 作为索引的数量 i 这样 A_i \neq B_i。 求最大可能距离 A 和 B.

约束

  • 1 \leq N \leq 100000
  • 0 \leq P_i \leq N-1
  • P_0,P_1,\cdots,P_{N-1} 都是不同的。
  • 0 \leq Q_i \leq N-1
  • Q_0,Q_1,\cdots,Q_{N-1} 都是不同的。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
P_0 P_1 \cdots P_{N-1}
Q_0 Q_1 \cdots Q_{N-1}

输出

打印最大可能距离 A 和 B.


示例输入 1

4
2 1 3 0
0 2 3 1

示例输出 1

3

例如,如果我们使 A=(0,1,2,3) 和 B=(0,2,3,1),距离将为 3,这是可能的最大结果。


示例输入 2

10
0 4 5 3 7 8 2 1 9 6
3 8 5 6 4 0 2 1 7 9

示例输出 2

8

示例输入 3

32
22 31 30 29 7 17 16 3 14 9 19 11 2 5 10 1 25 18 15 24 20 0 12 21 27 4 26 28 8 6 23 13
22 3 2 7 17 9 16 4 14 8 19 26 28 5 10 1 25 18 15 13 11 0 12 23 21 20 29 24 27 6 30 31

示例输出 3

28