题目描述

给定一个 $N \times N$ 的矩阵，你需要向其中填入 $0$ 或 $1$，使其满足以下条件：

• $(A_1,B_1),(A_2,B_2),...,(A_M,B_M)$ 处的值为 $1$。
• 第 $i$ 行的所有数字之和为 $M$ $(1 \le i \le N)$。
• 第 $i$ 列的所有数字之和为 $M$ $(1 \le i \le N)$。

输入格式

第一行有两个整数 $N$ 和 $M$。

接下来有 $M$ 行，第 $i+1$ 行有两个整数 $A_i$ 和 $B_i$。

输出格式

第一行输出矩阵中 $1$ 的个数 $k$。

接下来有 $k$ 行，第 $i+1$ 行输出两个整数 $x_i$ 和 $y_i$，表示 $(x_i,y_i)$ 处的值为 $1$。（顺序任意）

样例 1

输入

4 2
1 4
3 2

输出

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

样例 2

输入

3 3
3 1
2 3
1 3

输出

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

输出

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

说明/提示

约束条件

• $1 \le N \le 10^5$
• $1 \le M \le \min(N,10)$
• $1 \le A_i, B_i \le N$
• 当 $i \neq j$ 时，$(A_i, B_i) \neq (A_j, B_j)$。

样例解释 1

该输出按以下方式填充网格。所有条件均被满足，因此该输出是正确的。

0101
1001
0110
1010