まず、操作によって得られる \(A\) の特徴を考えます。実は、以下の \(2\) つの条件は同値になります：

• \(A=(1,2,\ldots,N)\) から \(N-1\) 回の操作によって \(C\) が得られる。
• \(i\) から \(C_i\) に辺を張ったようなグラフが \(1\) つのサイクルをなす。

これは \(N\) に関する帰納法で証明することができます。

頂点 \(A_i\) から \(B_i\) に辺を張ったようなグラフを \(G\) とします。もし \(G\) がオイラー閉路（グラフのすべての辺をちょうど \(1\) 回ずつ通って出発点に戻る閉路）を持つならば答えは \(N\) です。以降は \(G\) がオイラー閉路を持たない場合を考えます。

上の事実を用いると、問題は以下のように帰着させることができます。

\(G\) がオイラー閉路を持つようにするために \(B_i\) を書き換える回数の最小値は？

\(N\) からこの問題の答えを引いた値が本問題の答えとなります。以降はこの問題を考えます。

さらに、この問題の答えは以下と一致します。

\(G\) の辺をいくつかの trail に分解したときに、trail の本数としてあり得る最小値は？

（辺の本数が \(1\) 以上であるような）各連結成分について考えます。各連結成分は最低でも \(1\) 本の trail になります。また、出次数が入次数より大きい頂点ではその差分だけ trail の終点を作る必要があるので、連結成分内の頂点の集合を \(S\)、頂点 \(v\) の入次数を \(\text{in}[v]\)、出次数を \(\text{out}[v]\) として \(\displaystyle \sum_{v\in S} \max(0, \text{out}[v] - \text{in}[v])\) 本の trail が必要です。この \(2\) つを合わせ、各連結成分に対し trail の本数としてあり得る最小値は \(\displaystyle\max\left(1,\sum_{v\in S} \max(0, \text{out}[v] - \text{in}[v])\right)\) であることが分かります。この値を全ての連結成分に対して足し合わせた値が上の問題の答えとなります。

以上を適切に実装することでこの問題に正答することができます。

実装例(Python3)

import sys
from atcoder import dsu

input = sys.stdin.readline
for _ in range(int(input())):
    n = int(input())
    a = [x - 1 for x in map(int, input().split())]
    b = [x - 1 for x in map(int, input().split())]
    x = [0] * n
    y = [0] * n
    for c in a:
        x[c] += 1
    for c in b:
        y[c] += 1
    d = dsu.DSU(n)
    for i in range(n):
        d.merge(a[i], b[i])
    all_ok = d.size(a[0]) == len(set(a))
    for i in range(n):
        all_ok &= x[i] == y[i]
    if all_ok:
        print(n)
        continue
    ans = n
    for g in d.groups():
        if len(g) == 1 and x[g[0]] == 0 and y[g[0]] == 0:
            continue
        res = 0
        for c in g:
            res += max(0, y[c] - x[c])
        ans -= max(1, res)
    print(ans)