A - 01 Matrix Again Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

N \times N のマス目があります。上から i 行目、左から j 列目のマスを (i,j) と呼びます。

これから各マスに 0 か 1 を書き込みます。以下の条件を全て満たすように書き込む方法を一つ構築してください。

  • M 個のマス (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
  • i \neq j ならば (A_i,B_i) \neq (A_j,B_j)

入力

入力は以下の形式で標準入力から与えられる。

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

出力

1 を書き込むマスをマス (x_1,y_1),(x_2,y_2),\dots,(x_k,y_k) としたとき、以下のように出力せよ。

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

Score: 400 points

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