F. Удаление ранга
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Фермер Джон играет в игру, связанную с бинарной матрицей размера $$$n \times n$$$, обозначенной $$$M$$$. В этой задаче все $$$\href{https://ru.wikipedia.org/wiki/Ранг_матрицы}{\text{ранги}}$$$ матриц вычисляются над полем $$$\mathbb{F}_2$$$. Изначально гарантируется, что ранг $$$M$$$ равен $$$n$$$.

В начале хода пусть $$$r$$$ — ранг текущей матрицы $$$M$$$. Фермер Джон должен выбрать ровно $$$r$$$ различных элементов матрицы $$$M$$$, равных $$$1$$$, и заменить их все на $$$0$$$.

Фермер Джон хочет превратить $$$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$$$.

Все остальные элементы $$$M$$$ равны $$$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$$$ в текущей матрице перед ходом. Все ячейки, выбранные на одном ходу, должны быть различными.

Если существует несколько оптимальных последовательностей ходов, можно вывести любую из них.

Пример
Входные данные
2
2 2
1 1
2 2
3 5
1 1
1 2
2 2
2 3
3 3
Выходные данные
1
2
1 1
2 2
2
3
1 2
2 3
3 3
2
1 1
2 2
Примечание

В первом наборе входных данных дана матрица

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