P10683 [COTS 2024] Partition Particija

Translated from [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D2T1。$\texttt{1s,512M}$。

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$。

**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$。

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

#### 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$。 | Subtask ID | Score | Constraints | |:-----:|:------:|:-------:| | $1$ | $7$ | $k=0,N\le 8,\sum 2^N\le 10^5$ | | $2$ | $23$ | $k=0$ | | $3$ | $15$ | $k=1,N\le 1\, 000,\sum N^2\le 10^6$ | | $4$ | $16$ | $k=1$ | | $5$ | $19$ | $k=2,N\le 1\, 000,\sum N^2\le 10^6$ | | $6$ | $20$ | $k=2$ | Translated by ChatGPT 5