CF2262F.Rank Removal

Farmer John is playing a game involving an $n \times n$ binary matrix $M$. Throughout this problem, all matrix $\href{https://en.wikipedia.org/wiki/Rank_(linear_algebra)}{\text{ranks}}$ are computed over the field $\mathbb{F}_2$. Initially, the rank of $M$ is guaranteed to be $n$.

On a move, let $r$ be the rank of the current matrix $M$. Farmer John must choose exactly $r$ distinct entries of $M$ that are equal to $1$ and change all of them to $0$.

Farmer John wants to turn $M$ into the zero matrix using the minimum possible number of moves.

For each test case, output the minimum number of moves and any sequence of moves that achieves it.

农夫约翰正在玩一个涉及 $n \times n$ 二进制矩阵 $M$ 的游戏。在本题中，所有矩阵的 $\href{https://en.wikipedia.org/wiki/Rank_(linear_algebra)}{\text{秩}}$ 均在域 $\mathbb{F}_2$ 上计算。初始时，矩阵 $M$ 的秩保证为 $n$。

在一次操作中，设当前矩阵 $M$ 的秩为 $r$。农夫约翰必须恰好选择 $M$ 中 $r$ 个互不相同的值为 $1$ 的元素，并将它们全部变为 $0$。

农夫约翰希望以最少的操作次数将 $M$ 变为零矩阵。

对每个测试用例，输出最少操作次数，以及任意一个达到该次数的操作序列。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 300, n \le m \le n^2$) — the size of the matrix and the number of entries equal to $1$.

Each of the next $m$ lines contains two integers $x_i$ and $y_i$ ($1 \le x_i,y_i \le n$), denoting that $M_{x_i,y_i}=1$.

All other entries of $M$ are equal to $0$.

It is guaranteed that all given cells are distinct.

It is guaranteed that the rank of $M$ over $\mathbb{F}_2$ is $n$ for every test case.

It is guaranteed that the sum of $m$ over all test cases does not exceed $300^2$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

矩阵 $M$ 中其余所有元素均为 $0$。

保证所有给定的单元格互不相同。

保证对于每个测试用例，矩阵 $M$ 在 $\mathbb{F}_2$ 上的秩均为 $n$。

保证所有测试用例的 $m$ 值之和不超过 $300^2$。

For each test case, first output an integer $k$ — the minimum number of moves needed to turn $M$ into the zero matrix.

Then output $k$ lines, each describing one move.

For each move, let $r$ be the rank of the current matrix before the move. Output the integer $r$ on a new line. Then, output $r$ pairs of integers $x_i$ and $y_i$ representing the cells of a matrix we are changing to $0$.

For every $1 \le i \le r$, the cell $(x_i,y_i)$ must contain a $1$ in the current matrix before the move. All chosen cells in the same move must be distinct.

If there are multiple optimal sequences of moves, you may output any of them.

对于每个测试用例，首先输出一个整数 $k$ —— 将矩阵 $M$ 变为零矩阵所需的最少移动次数。

然后输出 $k$ 行，每行描述一次移动。

对于每次移动，设 $r$ 为本次移动前当前矩阵的秩。在新的一行中输出整数 $r$；接着输出 $r$ 对整数 $x_i$ 和 $y_i$，表示本次移动中被置为 $0$ 的矩阵单元格坐标。

对每个 $1 \le i \le r$，单元格 $(x_i,y_i)$ 在本次移动前的当前矩阵中必须为 $1$。同一次移动中所选的所有单元格必须互不相同。

若存在多个最优移动序列，可输出其中任意一个。

For the first test case, the matrix is

\\left\[ \\begin{array}{cc} 1 & 0 \\\\ 0 & 1 \\end{array} \\right\].

Its rank is $2$, so we remove the two entries $(1,1)$ and $(2,2)$ in one move.

For the second test case, the initial matrix is

\\left\[ \\begin{array}{ccc} 1 & 1 & 0 \\\\ 0 & 1 & 1 \\\\ 0 & 0 & 1 \\end{array} \\right\].

Its rank is $3$. After removing $(1,2)$, $(2,3)$, and $(3,3)$, the matrix becomes

\\left\[ \\begin{array}{ccc} 1 & 0 & 0 \\\\ 0 & 1 & 0 \\\\ 0 & 0 & 0 \\end{array} \\right\],

which has rank $2$. We then remove $(1,1)$ and $(2,2)$ in the second move.

对于第一个测试用例，矩阵为

$$\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)$。