| 最后的烈火凯 — 杰里米·祖克曼,《降世神通:最后的气宗》 |
![]() |
令 $$$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 可以给他以下类型的线索:
- A 排名线索$$$r$$$ 将突出显示他手上所有剩余牌的位置,等级为$$$r$$$。
- A 颜色 $$$c$$$ 的颜色线索 将以颜色 $$$c$$$ 突出显示他手上所有剩余牌的位置。
仅当突出显示至少一张卡片时才可以提供线索。此外,在提供新线索之前,所有卡片都会重置为未突出显示的状态。
游戏开始时,Iroh 提供线索,然后 Zuko 打出一张牌,他们交替进行,直到棋盘上的所有牌都打出,或者某些牌以无效顺序打出。
Zuko 决定在轮到他时,他将始终打出手中最左边突出显示的牌。 Iroh 想要制作一系列线索,既能让 Zuko 按有效顺序出牌,又能让 Zuko 出牌。 最大限度地减少线索与上一回合相比发生变化的回合数.
计算 Iroh 的线索在回合之间可能改变的最小次数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5, 1 \leq n \cdot m \leq 2 \cdot 10^5$$$) - 分别是排名和颜色的数量。
每个测试用例的第二行包含 $$$n \cdot m$$$ 整数 $$$r_1, r_2, \ldots, r_{n \cdot m}$$$ ($$$1 \leq r_i \leq n$$$),即 Zuko 手中牌从左到右的排名。
每个测试用例的第三行包含 $$$n \cdot m$$$ 整数 $$$c_1, c_2, \ldots, c_{n \cdot m}$$$ ($$$1 \leq c_i \leq m$$$),即 Zuko 手中从左到右的牌的颜色。
保证 $$$1 \leq r \leq n$$$、$$$1 \leq c \leq m$$$ 的每张牌 $$$(r, c)$$$ 在给定的手牌中出现一次 $$$(r_1, c_1), (r_2, c_2), \ldots, (r_{n \cdot m}, c_{n \cdot米})$$$。
保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - Iroh 的线索在回合之间可能发生变化的最小次数。可以证明,总是可以按照有效的顺序打出所有牌。
示例
输入复制
73 21 2 3 1 2 31 1 1 2 2 22 22 1 2 11 2 2 11 71 1 1 1 1 1 17 6 5 4 3 2 15 11 4 2 3 51 1 1 1 18 31 1 1 3 2 2 5 3 3 6 4 4 7 5 5 8 6 6 2 7 7 4 8 81 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 39 42 1 1 2 3 2 3 5 3 6 5 6 7 7 8 5 9 9 4 4 8 1 2 3 6 7 8 4 5 6 9 1 4 7 9 84 2 1 2 2 1 4 2 1 2 1 1 1 2 2 4 1 2 2 1 1 3 3 3 4 4 4 3 3 3 4 4 4 3 3 36 22 1 3 2 4 3 5 4 6 6 1 51 2 1 2 1 2 1 2 1 2 1 2
输出复制
1103684
注意
在第一个测试用例中,最佳移动顺序如下:
- Iroh 给出了颜色 $$$1$$$ 的颜色线索。
- 在接下来的三个回合中,Zuko 按顺序打出等级 $$$1、2$$$ 和 $$$3$$$ 颜色为 $$$1$$$ 的牌。
- Iroh 给出了颜色 $$$2$$$ 的颜色线索。
- 在接下来的三个回合中,Zuko 按顺序打出等级 $$$1、2$$$ 和 $$$3$$$ 颜色为 $$$2$$$ 的牌。
在第二个测试用例中,最佳移动顺序如下:
- Iroh 给出了排名 $$$1$$$ 的排名线索。
- 在接下来的两个回合中,Zuko 按顺序打出颜色为 $$$2$$$ 和 $$$1$$$ 的等级 $$$1$$$ 牌。
- Iroh 给出了排名 $$$2$$$ 的排名线索。
- 在接下来的两个回合中,Zuko 按顺序打出颜色为 $$$1$$$ 和 $$$2$$$ 的等级 $$$2$$$ 牌。
在第三个测试用例中,最佳移动顺序如下:
- Iroh 给出了排名 $$$1$$$ 的排名线索。
- 在接下来的七回合中,Zuko 按顺序打出 $$$1$$$ 颜色 $$$7、6、5、4、3、2、1$$$ 的牌。
在第四个测试用例中,最佳移动顺序如下:
- Iroh 给出了排名 $$$1$$$ 的排名线索。
- Zuko 打出等级为 $$$1$$$ 且颜色为 $$$1$$$ 的牌。
- Iroh 给出了排名 $$$2$$$ 的排名线索。
- Zuko 打出了等级 $$$2$$$ 颜色 $$$1$$$ 的牌。
- Iroh 给出了排名 $$$3$$$ 的排名线索。
- Zuko 打出等级 $$$3$$$ 颜色为 $$$1$$$ 的牌。
- Iroh 给出了颜色 $$$1$$$ 的颜色线索。
- Zuko 按顺序打出等级 $$$4$$$ 和等级 $$$5$$$ 颜色 $$$1$$$ 的牌。
