题目背景

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

题目描述

给定正整数 $N$。定义集合 $\{1, 2, \ldots, N\}$ 的一个划分是指一个由非空集合组成的集族，其中每个 $1\sim N$ 中的整数出现在恰好一个集合中。例如，$\{\{1,3\},\{2,4\},\{5\}\}$ 是集合 $\{1, 2, 3, 4, 5\}$ 的一个划分。

可以用数列 $x_1, x_2, \ldots, x_N$ 来表示一个划分，其中 $1 \leq x_i \leq 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$。

输出格式

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

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

提示

样例解释

样例 $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$