← 返回题目列表

AtCoder · arc176_a

A. 01 再次矩阵

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有一个 N \times N 网格。让 (i, j) 表示位于 i从顶部算起的第行和 j左起第 列。

您将用以下内容填充每个单元格 0 or 1。构造一种方法来填充满足以下所有条件的网格:

  • 细胞 (A_1,B_1), (A_2,B_2), \dots, (A_M,B_M) 包含 1.
  • 中的整数 i第行总和为 M. (1 \le i \le N)
  • 中的整数 i第列总和为 M. (1 \le i \le N)

可以证明,在本问题的约束下,至少有一种方法可以填充满足条件的网格。

约束

  • 1 \le N \le 10^5
  • 1 \le M \le \min(N,10)
  • 1 \le A_i, B_i \le N
  • (A_i, B_i) \neq (A_j, B_j) if i \neq j.

输入

输入由标准输入按以下格式给出:

N M
A_1 B_1
A_2 B_2
\vdots
A_{M} B_{M}

输出

让 (x_1,y_1), (x_2,y_2), \dots, (x_k,y_k) 是包含的单元格 1,并打印以下内容:

k
x_1 y_1
x_2 y_2
\vdots
x_k y_k

如果多个方法满足条件,则任何一个都被认为是正确的。


示例输入 1

4 2
1 4
3 2

示例输出 1

8
1 2
1 4
2 1
2 4
3 2
3 3
4 1
4 3

该输出填充网格如下。所有条件都满足,所以这个输出是正确的。

0101
1001
0110
1010

示例输入 2

3 3
3 1
2 3
1 3

示例输出 2

9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

示例输入 3

7 3
1 7
7 6
6 1

示例输出 3

21
1 6
2 4
4 1
7 3
3 6
4 5
6 1
1 7
7 6
3 5
2 2
6 3
6 7
5 4
5 2
2 5
5 3
1 4
7 1
4 7
3 2