First, let us consider the characteristics of \(A\) that can be obtained by the operations. In fact, the following two conditions are equivalent:

• \(C\) can be obtained from \(A=(1,2,\ldots,N)\) by \(N-1\) operations.
• The graph formed by drawing an edge from \(i\) to \(C_i\) forms a single cycle.

This can be proved by induction on \(N\).

Let \(G\) be the graph formed by drawing an edge from \(A_i\) to \(B_i\). If \(G\) has an Eulerian circuit, the answer is \(N\). Below, we consider the case where \(G\) does not have an Eulerian circuit.

Using the above fact, the problem can be reduced to the following.

What is the minimum number of times one needs to rewrite the value of \(B_i\) so that \(G\) has an Eulerian circuit (a circuit that traverses every edge of the graph exactly once and returns to the starting point)?

The answer to the original problem is \(N\) minus the answer to this problem. Below, we consider this problem.

Furthermore, the answer to this problem equals the following.

What is the minimum possible number of trails when the edges of \(G\) are decomposed into trails?

Consider each connected component (with at least one edge). Each connected component requires at least one trail. Also, at a vertex where the out-degree exceeds the in-degree, we need to create that many trail endpoints, so letting \(S\) be the set of vertices in a connected component, and \(\text{in}[v]\) and \(\text{out}[v]\) be the in-degree and out-degree of vertex \(v\), we need \(\displaystyle \sum_{v\in S} \max(0, \text{out}[v] - \text{in}[v])\) trails. Combining these two, the minimum possible number of trails for each connected component is \(\displaystyle\max\left(1,\sum_{v\in S} \max(0, \text{out}[v] - \text{in}[v])\right)\). The sum of this value over all connected components is the answer to the above problem.

By implementing the above appropriately, you can solve this problem.

Implementation example (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)