Score: $400$ points

问题陈述

有一个 $N \times N$ 的网格。用 $(i, j)$ 表示从顶部数第 $i$ 行，从左边数第 $j$ 列的单元格。

你需要用 $0$ 或 $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)$

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

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

There is an $N \times N$ grid. Let $(i, j)$ denote the cell at the $i$-th row from the top and the $j$-th column from the left.

You are to fill each cell with $0$ or $1$. Construct one method to fill the grid that satisfies all of the following conditions:

• The cells $(A_1,B_1), (A_2,B_2), \dots, (A_M,B_M)$ contain $1$.
• The integers in the $i$-th row sum to $M$. $(1 \le i \le N)$
• The integers in the $i$-th column sum to $M$. $(1 \le i \le N)$

It can be proved that under the constraints of this problem, there is at least one method to fill the grid that satisfies the conditions.

Constraints

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

Input

The input is given from Standard Input in the following format:

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_{M}$ $B_{M}$

Output

Let $(x_1,y_1), (x_2,y_2), \dots, (x_k,y_k)$ be the cells that contain $1$, and print the following:

$k$

$x_1$ $y_1$

$x_2$ $y_2$

$\vdots$

$x_k$ $y_k$

If multiple methods satisfy the conditions, any of them will be considered correct.

Sample Input 1

4 2
1 4
3 2

Sample Output 1

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

This output fills the grid as follows. All the conditions are satisfied, so this output is correct.

0101
1001
0110
1010

Sample Input 2

3 3
3 1
2 3
1 3

Sample Output 2

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

Sample Input 3

7 3
1 7
7 6
6 1

Sample Output 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