P10683 [COTS 2024] 划分 Particija

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

给定正整数 $ N $。 集合 $ \{1, 2, \ldots, N\} $ 的**划分**为由非空集合组成的集族，满足： - $\forall 1\le i\le N$，$i$ 出现在**恰好一个**集合中。 例如，$\{\{1,3\},\{2,4\},\{5\}\}$ 是集合 $ \{1, 2, 3, 4, 5\} $ 的一个划分。 可以用数列 $ [x_1, x_2, \ldots, x_N ]$ 来表示划分。当且仅当 $ x_i = x_j $ 时，$ i $ 和 $ j $ 在同一个集合中。上面提到的划分 $\{\{1,3\},\{2,4\},\{5\}\}$ 可以由数列 $[1, 2, 1, 2, 3]$ 或者 $[5, 1, 5, 1, 4]$ 表示。 Patricija 拥有两个划分：第一个划分用数列 $ [a_1, a_2, \ldots, a_N] $ 表示，第二个划分用数列 $ [b_1, b_2, \ldots, b_N] $ 表示。 Patricija 想知道以下问题的答案：如果她使用这两个划分中的集合，来构造集合 $ \{1, 2, \ldots, N\} $ 的划分，至少需要多少个集合。 给定参数 $k\in \{0,1,2\}$， - 当 $k=0$ 时，你需要回答原问题的答案。 - 当 $k=1$ 时，允许更改 $2N$ 个数字（$a_1,\cdots,a_N,b_1,\cdots,b_N$）中**至多**一个，**最小化**构造划分需要的最少集合数。 - 当 $k=2$ 时，允许更改 $2N$ 个数字（$a_1,\cdots,a_N,b_1,\cdots,b_N$）中**至多**一个，**最大化**构造划分需要的最少集合数。 请注意，你需要保证在你修改后，$\forall 1\le i\le N$，$1\le a_i,b_i\le N$。

**本题单个测试点内有多组测试数据。** 第一行，两个整数 $T,k$，分别表示测试数据数量，以及参数。 接下来依次描述 $T$ 组测试数据： 对于每组测试数据，输入三行。 第一行，一个正整数 $N$，含义见题面； 第二行，$N$ 个正整数，依次表示 $a_1,a_2,\cdots,a_N$； 第三行，$N$ 个正整数，依次表示 $b_1,b_2,\cdots,b_N$。

对于每组测试数据，输出一行一个整数，表示所求的答案。

#### 样例解释 样例 $1$ 解释： 对于第一组数据，第一个划分为 $\{\{1,2\},\{3\},\{4\}\}$，第二个划分为 $\{\{1\},\{2\},\{3,4\}\}$。选取 $\{1,2\},\{3,4\}$ 即可。 对于第二组数据，第一个划分为 $\{\{1,2,3,4\},\{5\},\{6\},\{7\}\}$，第二个划分为 $\{\{1\},\{2\},\{3\},\{4,5,6,7\}\}$。选取第一个划分或第二个划分即可。 #### 数据范围 对于 $100\%$ 的数据，保证： - $1\le T\le 200\, 000$，$k\in \{0,1,2\}$； - $1\le a_i,b_i\le N$； - $1\le N,\sum N\le 200\, 000$。 | 子任务编号 | 分值 | 约束 | |:-----:|:------:|:-------:| | $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$ |