← 返回题目列表

Codeforces · 2121/C

C. 那些和我们在一起的人

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

给定一个整数矩阵,其中包含 $$$n$$$ 行和 $$$m$$$ 列。第 $$$i$$$ 行和第 $$$j$$$ 列交叉处的单元格包含数字 $$$a_{ij}$$$。

您可以执行以下操作 正好一次:

  • 选择两个数字 $$$1 \leq r \leq n$$$ 和 $$$1 \leq c \leq m$$$。
  • 对于矩阵中满足 $$$i = r$$$ 或 $$$j = c$$$ 的所有单元格 $$$(i, j)$$$,将 $$$a_{ij}$$$ 减一。

在执行一次此类操作后,您需要找到矩阵 $$$a$$$ 中的最小可能最大值。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \cdot m \leq 10^5$$$) - 矩阵中的行数和列数。

每个测试用例的接下来 $$$n$$$ 行描述矩阵 $$$a$$$。第 $$$i$$$ 行包含 $$$m$$$ 整数 $$$a_{i1}, a_{i2}, \ldots, a_{im}$$$ ($$$1 \leq a_{ij} \leq 100$$$) — 矩阵第 $$$i$$$ 行中的元素。

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

输出

对于每个测试用例,在执行一次操作后输出矩阵 $$$a$$$ 中的最小最大值。

示例

输入
复制

10
1 1
1
1 2
1 2
2 1
2
1
2 2
4 2
3 4
3 4
1 2 3 2
3 2 1 3
2 1 3 2
4 3
1 5 1
3 1 3
5 5 5
3 5 1
4 4
1 3 3 2
2 3 2 2
1 2 2 1
3 3 2 3
2 2
2 2
1 2
3 2
1 2
2 1
1 2
3 3
2 1 1
1 2 1
1 1 2

输出
复制

0
1
1
3
2
4
3
1
1
2

注意

在前三个测试用例中,您可以选择 $$$r = 1$$$ 和 $$$c = 1$$$。

在第四个测试用例中,您可以选择 $$$r = 1$$$ 和 $$$c = 2$$$。

在第五个测试用例中,您可以选择 $$$r = 2$$$ 和 $$$c = 3$$$。

在第六个测试用例中,您可以选择 $$$r = 3$$$ 和 $$$c = 2$$$。