思路

• 图建模：对每个位置 $i$，连无向边 $(a_i, b_i)$。则图的每个连通块中的所有值最终必须被“合并”为同一个值。
• 关键结论：若某连通块包含 $k$ 个不同值，至少需要 $k-1$ 次操作（每次操作最多将不同值的种类数减少 $1$），且可沿生成树依次合并达到该下界。
• 答案：设 $K$ 为在 $a\cup b$ 中出现的不同值总数，$C$ 为上述图的连通块个数，则最少操作数为 $K - C.$

本题为2025年8月31日拼多多机考原题

拼多多机考的介绍点击这里

题目内容

多多有两个长度为 $n$ 的正整数序列 $a,b$，序列中的元素值是不超过 $m$ 的正整数，即对于任意 $1≤i≤n$ , 满足 $1 ≤ a_i,b_i ≤ m$ 。

一次操作包括下列步骤：

1.仼选 $x,y$ ，满足 $1≤x,y≤m$ 。

2.对于仼意 $i(1 ≤i≤ n)$ ，如果 $a_i=x$ ，则将 $a_i$ 赋值为 $y$ 。

3.对于仼意 $i(1 ≤i≤ n)$ ，如果 $b_i=x$ ，则将 $b_i$ 赋值为 $y$ 。

可以进行上述操作任意多次，问最少需要多少次操作，可以使得序列 $a$ 与 $b$ 变得完全相同。

输入描述

第一行为一个整数 $T$ ，表示共有 $T$ 组测试数据 $(1 ≤ T ≤1000)$ 。

接下来每组测试数据，第一行为两个整数 $n,m(1≤n<10^5,1≤m≤10^6)$ 。

第二行为序列 $a$ 中的 $n$ 个正整数，

第三行为序列 $b$ 中的 $n$ 个正整数。

对于 $T$ 组数据， $n$ 的总和不超过 $10^5$ ，$m$ 的总和不超过 $10^6$ 。

输出描述

对于每组测试数据，在单独的一行里输出所需的最少操作数。

样例1

输入

3
3 8
2 5 1
2 5 1
3 8
2 5 1
5 2 1
3 8
2 5 2
5 2 1

输出

0
1
2

说明

对于第一个数据，可以选取 $x=2,y=5$ ，操作完成后，两个序列都会变成 $[5,5,1]$ 。

对于第三个数据，可以操作两次：

1.选取 $x=2,y=1$ ，操作后，$a=[1,5,1],b=[5,1,1]$ 。

2.选取 $x=1,y=5$ ，操作后，$a=[5,5,5],b=[5,5,5]$ 。