CF2262F Rank Removal

农场主 John 正在玩一个与 $n \times n$ 二进制矩阵 $M$ 有关的游戏。在本题目中，所有矩阵的 $\href{https://en.wikipedia.org/wiki/Rank_(linear_algebra)}{\text{秩}}$ 都是在域 $\mathbb{F}_2$ 上计算的。初始时，矩阵 $M$ 的秩保证为 $n$。 每次操作时，设当前矩阵 $M$ 的秩为 $r$。农场主 John 必须选择恰好 $r$ 个不同的、值为 $1$ 的矩阵条目，并将它们全部变为 $0$。 农场主 John 想用尽可能少的操作，将 $M$ 变成全零矩阵。 对于每个测试用例，输出最少的操作次数，以及实现最少操作次数的任意一种操作序列。

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 300,\, n \le m \le n^2$）——表示矩阵的大小以及 $1$ 的个数。 接下来的 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$），表示 $M_{x_i, y_i} = 1$。 矩阵中的其它所有位置的值均为 $0$。 保证所有给定的单元格都是不同的。 保证对每个测试用例，$M$ 在 $\mathbb{F}_2$ 下的秩为 $n$。 保证所有测试用例中 $m$ 的总和不超过 $300^2$。

对于每一个测试用例，首先输出一个整数 $k$，表示将 $M$ 变成全零矩阵所需的最少操作次数。 随后输出 $k$ 行，每行描述一次操作。 对于每次操作，设当前的矩阵秩为 $r$，则需要在新的一行中输出整数 $r$，接着输出 $r$ 对整数 $x_i$ 和 $y_i$，表示要变为 $0$ 的矩阵单元格坐标。 对于每个 $1 \le i \le r$，$(x_i, y_i)$ 必须是当前矩阵中值为 $1$ 的单元格。同一次操作内所有选择的坐标必须互不相同。 如果有多种不同的最优操作序列，可以输出其中任意一种。

第一个测试用例中，矩阵为 $$ \left[ \begin{array}{cc} 1 & 0 \\ 0 & 1 \end{array} \right]。 $$ 其秩为 $2$，所以我们可以一次性移除 $(1,1)$ 和 $(2,2)$ 这两个位置。 第二个测试用例中，初始矩阵为 $$ \left[ \begin{array}{ccc} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{array} \right]。 $$ 其秩为 $3$。移除 $(1,2)$、$(2,3)$ 和 $(3,3)$ 之后，矩阵变为 $$ \left[ \begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{array} \right]， $$ 其秩为 $2$，然后第二次操作移除 $(1,1)$ 和 $(2,2)$。 由 ChatGPT 5 翻译