P14197 [ICPC 2024 Hangzhou R] Kind of Bingo

有一个由 $n$ 行 $m$ 列组成的网格。网格中的每个单元格从 $1$ 到 $n \times m$ 编号，第 $i$ 行第 $j$ 列的单元格编号为 $((i - 1) \times m + j)$。 给定一个 $n \times m$ 长度的排列 $p_1, p_2, \cdots, p_{n \times m}$，我们将按照该排列进行 $n \times m$ 次操作。第 $i$ 次操作时，我们会标记单元格 $p_i$。如果在第 $b$ 次操作后，存在至少一行的所有单元格都被标记，并且 $b$ 尽可能小，则称 $b$ 为该排列的“bingo 数”。 你最多可以对该排列进行 $k$ 次修改（也可以不修改）。每次修改可以交换排列中的任意两个元素。请计算在最多经过 $k$ 次修改后，最小可能的 bingo 数。 注意，若一个长度为 $n \times m$ 的序列 $p_1, p_2, \cdots, p_{n \times m}$ 每个整数 $1$ 到 $n \times m$ 各出现一次，那么它是 $n \times m$ 的一个排列。

输入包含多组测试数据。第一行为整数 $T$（$1 \le T \le 10^4$），表示数据组数。每组测试数据输入如下： 第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m \le 10^5$，$1 \le n \times m \le 10^5$，$0 \le k \le 10^9$），分别表示网格的行数、列数和你可以进行交换的最大次数。 第二行包含 $n \times m$ 个不同的整数 $p_1, p_2, \cdots, p_{n \times m}$（$1 \le p_i \le n \times m$）。 保证所有测试数据中 $n \times m$ 的总和不超过 $10^5$。

对于每组测试数据，输出一行一个整数，表示经过最多 $k$ 次修改后，最小可能的 bingo 数。

对于第一个样例，我们可以先交换 $1$ 和 $15$，再交换 $6$ 和 $12$，得到序列 $[15, 4, 13, 12, 8, 11, 14, 2, 7, 10, 3, 1, 9, 5, 6]$。可以发现第 $7$ 次操作后，第 $3$ 行的所有单元格都被标记。 对于第二个样例，很容易发现第 $5$ 次操作后，第 $2$ 行的所有单元格都被标记。 对于第三个样例，不需要做任何修改。第 $3$ 次操作后，第 $1$ 行的所有单元格都被标记。 由 ChatGPT 5 翻译