You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

译自 Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) 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$。

输出格式

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

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