CF2207F.Hanabi

Last Agni Kai — Jeremy Zuckerman, Avatar: The Last Airbender

设 $n, m$ 均为正整数。Iroh 和 Zuko 正在玩一种变体的 Hanabi（花火）合作类纸牌游戏，其中有 $n$ 个等级（$1, \ldots, n$）和 $m$ 个颜色（$1, \ldots, m$）。Zuko 手中有 $n \cdot m$ 张卡牌，每种“等级-颜色”组合各一张。

在他回合时，他可以选择任意一张卡牌并打出。但如果他打出一张等级为 $r \geq 2$ 且颜色为 $c$ 的牌，但等级为 $r-1$ 且颜色为 $c$ 的牌还没被打出，则游戏失败。

为了使游戏更加有趣，Zuko“反向拿牌”，也就是他将所有手牌牌面朝向 Iroh，使只有 Iroh 可以看到它们的等级和颜色。为了给 Zuko 提供信息，每回合 Iroh 可以给出以下两种“线索”之一：

• 对于等级 $r$，等级线索会高亮所有手牌中等级为 $r$ 的未出牌卡牌的位置。
• 对于颜色 $c$，颜色线索会高亮所有手牌中颜色为 $c$ 的未出牌卡牌的位置。

仅当线索能高亮至少一张牌时，该线索才可被给出。另外，在给出新线索前，所有牌均会复位为未高亮状态。

游戏开始时由 Iroh 给出线索，然后 Zuko 打一张牌，二者轮流，直到所有牌均已正确打出或出现违序出牌导致失败。

Zuko 决定：他的每次出牌总会选择高亮区域最靠左的一张牌打出。Iroh 希望给出一系列线索，既能保证 Zuko 可以按照规则顺序出完所有牌，又能最小化其线索内容相对于前一次回合发生改变的次数。

请你计算 Iroh 至少需要变化多少次线索内容，才能满足上述要求。

每组测试数据包含多个测试用例。第一行包含测试用例个数 $t$（$1 \leq t \leq 10^4$）。每组测试用例的描述如下：

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2 \times 10^5,\ 1 \leq n \cdot m \leq 2 \times 10^5$），分别表示等级数和颜色数。

第二行包含 $n \cdot m$ 个整数 $r_1,r_2,\ldots,r_{n \cdot m}$（$1 \leq r_i \leq n$），表示 Zuko 手中第 $i$ 张牌的等级（从左到右的顺序）。

第三行包含 $n \cdot m$ 个整数 $c_1,c_2,\ldots,c_{n \cdot m}$（$1 \leq c_i \leq m$），表示 Zuko 手中第 $i$ 张牌的颜色（从左到右的顺序）。

保证每种 $(r, c)$ 卡牌（$1 \leq r \leq n,\ 1 \leq c \leq m$）恰好出现在手牌序列中一次。

确保所有测试用例中 $n \cdot m$ 总和不超过 $2 \times 10^5$。

对于每组测试用例，输出一个整数，表示 Iroh 的线索内容最少需要变化的次数。保证一定存在能将所有卡牌按规则全打出的方案。

在第一个测试用例中，最优动作序列如下：

• Iroh 给出颜色 $1$ 的颜色线索。
• 接下来三回合，Zuko 依次打出颜色 $1$ 的等级 $1, 2, 3$ 的卡牌。
• Iroh 给出颜色 $2$ 的颜色线索。
• 接下来三回合，Zuko 依次打出颜色 $2$ 的等级 $1, 2, 3$ 的卡牌。

Iroh 总计更改线索 $1$ 次，该结果为最优。

在第二个测试用例中，最优动作序列如下：

• Iroh 给出等级 $1$ 的等级线索。
• 接下来两回合，Zuko 依次打出颜色 $2, 1$ 的等级 $1$ 卡牌。
• Iroh 给出等级 $2$ 的等级线索。
• 接下来两回合，Zuko 依次打出颜色 $1, 2$ 的等级 $2$ 卡牌。

Iroh 更改线索 $1$ 次，该结果为最优。

在第三个测试用例中，最优动作序列如下：

• Iroh 给出等级 $1$ 的等级线索。
• 接下来七回合，Zuko 依次打出颜色 $7, 6, 5, 4, 3, 2, 1$ 的等级 $1$ 卡牌。

Iroh 更改线索 $0$ 次，该结果为最优。

在第四个测试用例中，最优动作序列如下：

• Iroh 给出等级 $1$ 的等级线索。
• Zuko 打出颜色 $1$ 的等级 $1$ 卡牌。
• Iroh 给出等级 $2$ 的等级线索。
• Zuko 打出颜色 $1$ 的等级 $2$ 卡牌。
• Iroh 给出等级 $3$ 的等级线索。
• Zuko 打出颜色 $1$ 的等级 $3$ 卡牌。
• Iroh 给出颜色 $1$ 的颜色线索。
• Zuko 依次打出颜色 $1$ 的等级 $4, 5$ 卡牌。

Iroh 总计更改线索 $3$ 次，该结果为最优。

由 ChatGPT 5 翻译