Background

Description

Once upon a time there was a kingdom whose castle was a rectangle of $m$ rows and $n$ columns, divided into $m \times n$ cells. Some cells are walls, and others are empty. The king has set traps in the castle, each trap occupying one empty cell.

One day, the king decided to deploy guards in the castle, and he wants to place as many guards as possible.

The guards are strictly trained, so as soon as they find someone in the same row or the same column, they immediately shoot at that person. Therefore, the king wants to place the guards so that they cannot see each other, making it impossible for them to shoot one another. Guards can only be placed on empty cells, not on traps or walls, and at most one guard can be placed on any empty cell. If two guards are in the same row or column and there is no wall between them, they can see each other (guards move like rooks in chess).

Your task is to write a program that, given the castle, computes the maximum number of guards that can be placed and outputs one optimal placement.

Output Format

This problem uses Special Judge.

First output a single integer $k$, the maximum number of guards that can be placed.

Then output $k$ lines. Each line contains two integers $x, y$, indicating that a guard is placed at row $x$ and column $y$.

3 4
2 0 0 0
2 2 2 1
0 1 0 2

2
1 2
3 3

Hint

Explanation for sample input and output 1:

As shown in the figure (black cells are walls, white cells are empty, circles are traps, and G denotes a guard).

Constraints:

For all testdata, it is guaranteed that $1 \leq m, n \leq 200$ and $0 \leq a_{i, j} \leq 2$.

Translated by ChatGPT 5