#agc038f. [agc038_f]Two Permutations

[agc038_f]Two Permutations

【题意简述】

给定两个 0(N1)0 \sim (N - 1) 的排列 {P0,P1,,PN1}\{P_0, P_1, \ldots , P_{N - 1}\}{Q0,Q1,,QN1}\{Q_0, Q_1, \ldots , Q_{N - 1}\}

要求构造两个 0(N1)0 \sim (N - 1) 的排列 {A0,A1,,AN1}\{A_0, A_1, \ldots , A_{N - 1}\}{B0,B1,,BN1}\{B_0, B_1, \ldots , B_{N - 1}\}

且必须满足条件:

  • AiA_i 要么等于 ii,要么等于 PiP_i
  • BiB_i 要么等于 ii,要么等于 QiQ_i

你需要最大化 AiBiA_i \ne B_i 的下标 ii 的数量,输出这个最大值。

【输入格式】

第一行一个整数 NN
第二行 NN 个整数 P0,P1,,PN1P_0, P_1, \ldots , P_{N - 1}
第三行 NN 个整数 Q0,Q1,,QN1Q_0, Q_1, \ldots , Q_{N - 1}

【输出格式】

输出一个整数表示答案。

【数据范围】

对于 100%100\% 的数据,1N1051 \le N \le {10}^5