Minimum Column Removal for Equal Sorted Rows

Luka drew a table with \(3\) rows and \(N\) columns. He then wrote the integers from \(1\) to \(N\) into the table. In the first row, every number appears exactly once (i.e. the first row is a permutation of \(1, 2, \dots, N\)). In the other two rows, each number may appear arbitrarily many times or not at all.

Now Luka is allowed to delete any set of columns (the same columns are deleted from all three rows). After deletion, he sorts each row in ascending order independently. He wishes the resulting three sorted rows to be identical (i.e. the multiset of numbers in each row is the same).

Formally, let the three rows be arrays \(A, B, C\) each of length \(N\) with \(A\) being a permutation of \(\{1, 2, \dots, N\}\). If we remove a set \(S\) of column indices, then the multiset of remaining values in row \(r\) is \(\{X_r[i] : i \notin S\}\) for \(r=1,2,3\). We require that after sorting, these three lists are identical. Equivalently, if we denote by \(S^c\) the set of columns kept (with \(|S^c| = k\)), and let for each number \(x\) the frequency be

[ f_r(x) = |{ i \in S^c : X_r[i] = x }|, \quad r = 1, 2, 3, ]

then we need for every (x):

[ f_1(x) = f_2(x) = f_3(x). ]

Since row 1 is a permutation, for every (x) we have (f_1(x) \in {0,1}). In other words, if the column where (A[i]=x) is kept then (x) must appear exactly once in each row in the kept columns; if it is deleted then (x) must not appear in any other position in rows 2 or 3.

It can be shown that a valid set of kept columns corresponds to choosing a subset \(X\subseteq\{1,2,\dots,N\}\) such that:

• If \(x\in X\), then the unique column \(i\) with \(A[i]=x\) is kept.
• For every \(x\in X\), the total number of kept columns \(i\) with \(B[i]=x\) is exactly \(1\) (and similarly for \(C[i]=x\)).

Define the functions

[ F_B(x) = B[\mathit{pos}_A(x)] \quad \text{and} \quad F_C(x) = C[\mathit{pos}_A(x)], ]

where (\mathit{pos}_A(x)) is the unique index such that (A[\mathit{pos}_A(x)] = x). Then the condition translates into requiring that for every (x\in X), in the induced functional graphs of (F_B) and (F_C) (which are functions from ({1,2,\dots,N}) to (\mathbb{N})), the restriction to (X) forms a permutation (i.e. every (x\in X) has exactly one preimage). In other words, only the numbers that lie on cycles in both of the functional graphs can be chosen.

Your task is to compute the minimum number of columns to delete, i.e. \(N - |X|\) where \(X\) is the largest possible subset of \(\{1,2,\dots,N\}\) that lies in a cycle in both graphs.

Input format:

1. The first line contains an integer \(N\) (the number of columns).
2. The second line contains \(N\) integers \(A[1], A[2], \dots, A[N]\), denoting the first row (a permutation of \(1,2,\dots,N\)).
3. The third line contains \(N\) integers \(B[1], B[2], \dots, B[N]\) for the second row.
4. The fourth line contains \(N\) integers \(C[1], C[2], \dots, C[N]\) for the third row.

Output format:

Output a single integer: the minimum number of columns that must be deleted so that after independently sorting the remaining rows, all three rows are identical.

inputFormat

The input consists of four lines. The first line is an integer \(N\). The second line contains \(N\) space‑separated integers representing the first row (a permutation of \(1\) to \(N\)). The third and fourth lines each contain \(N\) space‑separated integers representing the second and third rows, respectively.

outputFormat

Output a single integer: the minimum number of columns to delete.

sample

3
2 3 1
1 2 3
3 1 2

0