Minimum Partition Sets Using Two Partitions

You are given a positive integer \(N\) and two partitions of the set \(\{1,2,\ldots,N\}\). The first partition is represented by a sequence \([a_1,a_2,\ldots,a_N]\) and the second partition by \([b_1,b_2,\ldots,b_N]\). A partition of \(\{1,2,\ldots,N\}\) is defined as a family of nonempty disjoint sets whose union is \(\{1,2,\ldots,N\}\). In the representation, we have that for any \(i,j\) with \(1\le i,j\le N\), the equality \(x_i=x_j\) (where \(x\) represents either the sequence \(a\) or \(b\)) means that \(i\) and \(j\) lie in the same subset.

Using the two given partitions, Patricija wants to construct a partition of \(\{1,2,\ldots,N\}\) by choosing some of the subsets from the two partitions. Note that the chosen subsets must form a partition, meaning they are mutually disjoint and their union is \(\{1,2,\ldots,N\}\). For each element \(i\), notice that it appears exactly in one subset in the first partition and one subset in the second partition. Thus, you can think of each element as an edge connecting the block in the first partition that contains it and the block in the second partition that contains it. In other words, if we think of the blocks of the first partition as vertices on one side (denoted by A) and the blocks of the second partition as vertices on the other side (denoted by B), then for every element \(i\) there is an edge between \(A_{a_i}\) and \(B_{b_i}\>.

In such a bipartite graph, each connected component has a bipartition \(U\) (A‐side vertices) and \(V\) (B‐side vertices). One valid strategy to cover all the edges with a choice of vertices (each chosen vertex corresponding to selecting that block in the final partition) is to choose one of the two sides in every connected component. In a connected component, the number of chosen blocks will be \(\min(|U|,|V|)\). Therefore, for the given unmodified partitions, the minimum number of blocks needed is the sum of \(\min(|U|,|V|)\) over all connected components.

Furthermore, you are given a parameter \(k\in\{0,1,2\}\):

• When \(k=0\): compute the minimum number of subsets needed using the given partitions.
• When \(k=1\): you are allowed to change at most one element among all \(2N\) numbers (i.e. one of \(a_1, a_2,\ldots,a_N, b_1, b_2,\ldots,b_N\)) to any integer in \([1,N]\) (and not required to change any if not beneficial), in order to minimize the final answer.
• When \(k=2\): similarly, you are allowed to change at most one number among the \(2N\) numbers (if beneficial) to any integer in \([1,N]\) to maximize the final answer.

Note: After any modifications, the sequences must still satisfy \(1\le a_i,b_i\le N\) for \(1\le i\le N\>.

Input/Output Explanation: Think of each element \(i\) as yielding an edge between vertex \( (A, a_i) \) and vertex \( (B, b_i) \) in a bipartite graph. For each connected component, if the bipartition sizes are \(x\) and \(y\), then the cost for that component is \(\min(x,y)\). The answer is the sum of these costs over all components.

inputFormat

The first line contains two integers: \(k\) and \(N\), where \(k\in\{0,1,2\}\) and \(N\) is the size of the set.

The second line contains \(N\) integers: \(a_1, a_2, \ldots, a_N\) separated by spaces.

The third line contains \(N\) integers: \(b_1, b_2, \ldots, b_N\) separated by spaces.

outputFormat

Output a single integer: the minimum number of subsets required in the constructed partition according to the rules and the allowed modification (if any) given the value of \(k\).

sample

0 5
1 2 1 2 3
5 1 5 1 4

3