← 返回题目列表

Codeforces · 2069/B

B. 陌生人集

中文机器翻译题面 查看原题

将为您提供一个包含 $$$n$$$ 行和 $$$m$$$ 列的表。最初,第 $$$i$$$ 行和第 $$$j$$$ 列的单元格的颜色为 $$$a_{i, j}$$$。

假设两个单元格是 陌生人 如果他们 不要 分享一面。陌生人可以接触角落。

假设单元格集合是 一组陌生人 如果集合中的所有单元格对都是陌生人。根据定义,不超过一个单元的集合是陌生人集合。

只需一步,您就可以选择任意一组陌生人 使得其中的所有单元格具有相同的颜色 并将它们全部涂成其他颜色。您可以选择最终的颜色。

使整个表格颜色相同至少需要多少步?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。接下来是 $$$t$$$ 案例。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le m \le 700$$$) - 表中的行数和列数。

接下来的 $$$n$$$ 行包含相应行 $$$a_{i, 1}, \dots, a_{i, m}$$$ ($$$1 \le a_{i, j} \le nm$$$) 中单元格的颜色。

保证所有测试用例的 $$$nm$$$ 总和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 将表格的所有单元格绘制为相同颜色的最小步骤数。

示例

输入
复制

4
1 1
1
3 3
1 2 1
2 3 2
1 3 1
1 6
5 4 5 4 4 5
3 4
1 4 2 2
1 4 3 5
6 6 3 5

输出
复制

0
2
1
10

注意

在第一个测试用例中,表格从一开始就用一种颜色绘制。

在第二个测试用例中,例如,您可以选择颜色为 $$$1$$$ 的所有单元格并将它们绘制为 $$$3$$$。然后选择颜色为 $$$2$$$ 的所有单元格,并将它们绘制为 $$$3$$$。

在第三个测试用例中,您可以选择颜色为 $$$5$$$ 的所有单元格并将它们绘制为颜色 $$$4$$$。