Background

Translated from Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) D2T1。$\texttt{1s,512M}$。

Problem Description

You are given a positive integer $N$。

A partition of the set $\{1, 2, \ldots, N\}$ is a family of non-empty sets such that:

• $\forall 1\le i\le N$，$i$ appears in exactly one set。

For example, $\{\{1,3\},\{2,4\},\{5\}\}$ is a partition of the set $\{1, 2, 3, 4, 5\}$。

A partition can be represented by an array $[x_1, x_2, \ldots, x_N]$。Element $i$ and element $j$ are in the same set if and only if $x_i = x_j$。The partition $\{\{1,3\},\{2,4\},\{5\}\}$ mentioned above can be represented by $[1, 2, 1, 2, 3]$ or $[5, 1, 5, 1, 4]$。

Patricija has two partitions: the first one is represented by $[a_1, a_2, \ldots, a_N]$，and the second one is represented by $[b_1, b_2, \ldots, b_N]$。

Patricija wants to know the answer to the following question: if she uses sets from these two partitions to construct a partition of the set $\{1, 2, \ldots, N\}$，what is the minimum number of sets needed。

Given a parameter $k\in \{0,1,2\}$:

• When $k=0$，you need to answer the original question。
• When $k=1$，you are allowed to change at most one number among the $2N$ numbers ($a_1,\cdots,a_N,b_1,\cdots,b_N$)，and minimize the minimum number of sets needed to construct such a partition。
• When $k=2$，you are allowed to change at most one number among the $2N$ numbers ($a_1,\cdots,a_N,b_1,\cdots,b_N$)，and maximize the minimum number of sets needed to construct such a partition。

Note that after your modification, you must ensure that $\forall 1\le i\le N$，$1\le a_i,b_i\le N$。

Input Format

This problem contains multiple test cases within a single input file.

The first line contains two integers $T,k$，representing the number of test cases and the parameter.

Then $T$ test cases follow.

For each test case, the input contains three lines.

The first line contains a positive integer $N$，as described above.

The second line contains $N$ positive integers, representing $a_1,a_2,\cdots,a_N$。

The third line contains $N$ positive integers, representing $b_1,b_2,\cdots,b_N$。

Output Format

For each test case, output one line with one integer, representing the required answer。

2 0
4 
1 1 2 3
1 2 3 3
7
1 1 1 1 2 3 4
1 2 3 4 4 4 4

2
4

3 1
4
1 1 2 3
1 2 3 3
4
1 1 1 1
1 2 3 3
7
1 1 1 1 2 3 4
1 2 3 4 4 4 4

2
1
2

3 2
4 
1 1 2 3
1 2 3 3
4
1 1 1 3
1 2 3 3
7
1 1 1 2 3 4 5
1 2 3 4 4 4 4

3
3
4

Hint

Sample Explanation

Explanation for sample $1$:

For the first test case, the first partition is $\{\{1,2\},\{3\},\{4\}\}$，and the second partition is $\{\{1\},\{2\},\{3,4\}\}$。Choosing $\{1,2\},\{3,4\}$ is enough。

For the second test case, the first partition is $\{\{1,2,3,4\},\{5\},\{6\},\{7\}\}$，and the second partition is $\{\{1\},\{2\},\{3\},\{4,5,6,7\}\}$。Choosing either the first partition or the second partition is enough。

Constraints

For $100\%$ of the data, it is guaranteed that:

• $1\le T\le 2\times 10^5$，$k\in \{0,1,2\}$；
• $1\le a_i,b_i\le N$；
• $1\le N,\sum N\le 2\times 10^5$。

Translated by ChatGPT 5