codeforces

Prompt

题目：F. Rank Removal（秩消除） 时间限制：每个测试 2 秒 内存限制：每个测试 256 MB 【题目描述】 Farmer John 在玩一个涉及 n 行 n 列 0-1 矩阵 M 的游戏。在本题中，所有矩阵的秩都是在有限域 F2（即模 2 的域）上计算的。初始时，保证矩阵 M 的秩为 n。 每次操作时，设 r 为当前矩阵 M 的秩。Farmer John 必须恰好选择 r 个互不相同、且当前值等于 1 的矩阵元素，并把它们全部变成 0。 Farmer John 想用最少的操作次数把 M 变成零矩阵。 对于每个测试用例，输出最少的操作次数，以及任意一组合法的操作方案。 【输入格式】 每个测试包含多个测试用例。第一行包含测试用例的数量 t（1 ≤ t ≤ 10000）。接下来是各测试用例的描述。 每个测试用例的第一行包含两个整数 n 和 m（2 ≤ n ≤ 300，n ≤ m ≤ n 的平方），分别表示矩阵的大小和值等于 1 的元素个数。 接下来的 m 行中，每行包含两个整数 xi 和 yi（1 ≤ xi ≤ n，1 ≤ yi ≤ n），表示矩阵中第 xi 行第 yi 列的元素 M[xi][yi] 等于 1。 矩阵 M 的所有其他元素都等于 0。 保证给出的所有格子互不相同。 保证每个测试用例中矩阵 M 在域 F2 上的秩为 n。 保证所有测试用例的 m 之和不超过 300000。 【输出格式】 对于每个测试用例，首先输出一个整数 k，即把 M 变成零矩阵所需的最少操作次数。 然后输出 k 行，每行描述一次操作。 对于每次操作，设 r 为该操作执行前当前矩阵的秩。先单独输出一行整数 r。然后输出 r 对整数 xi 和 yi，表示本次要变为 0 的那些格子。 对于每次操作中的每个 i（1 ≤ i ≤ r），格子 (xi, yi) 在该操作执行前必须包含 1。同一次操作中选出的所有格子必须互不相同。 如果存在多个最优操作序列，输出其中任意一个即可。 【样例输入】 2 2 2 1 1 2 2 3 5 1 1 1 2 2 2 2 3 3 3 样例输入说明：第 1 个测试用例中 n=2，m=2，值为 1 的格子是 (1,1) 和 (2,2)；第 2 个测试用例中 n=3，m=5，值为 1 的格子是 (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 样例输出说明：第 1 个测试用例最少操作次数为 1，第一次操作时秩 r=2，选择格子 (1,1) 和 (2,2) 置 0。第 2 个测试用例最少操作次数为 2，第一次操作时秩 r=3，选择格子 (1,2)、(2,3)、(3,3) 置 0；第二次操作时秩 r=2，选择格子 (1,1) 和 (2,2) 置 0。 【样例解释】 第 1 个测试用例的初始矩阵是一个 2 行 2 列矩阵：第 1 行从左到右为 1, 0；第 2 行从左到右为 0, 1。它的秩是 2，所以我们在一次操作中同时移除 (1,1) 和 (2,2) 这两个元素。 第 2 个测试用例的初始矩阵是一个 3 行 3 列矩阵：第 1 行从左到右为 1, 1, 0；第 2 行从左到右为 0, 1, 1；第 3 行从左到右为 0, 0, 1。它的秩是 3。移除 (1,2)、(2,3) 和 (3,3) 之后，矩阵变为：第 1 行从左到右为 1, 0, 0；第 2 行从左到右为 0, 1, 0；第 3 行从左到右为 0, 0, 0。此时矩阵的秩为 2，于是我们在第二次操作中移除 (1,1) 和 (2,2)。 请用cpp解决上面这个题，自己思考不要上网查答案