分数: 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