F. Rank Removal
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

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.

Example
Input
2
2 2
1 1
2 2
3 5
1 1
1 2
2 2
2 3
3 3
Output
1
2
1 1
2 2
2
3
1 2
2 3
3 3
2
1 1
2 2
Note

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.