Black-and-white Square

Interview

Time limit1sMemory limit256 MB

Summary

Decide whether the black cells equal the union of some full rows and columns and print the smallest stripe set.

Level: Medium5 of 10
Topics: Matrix, Implementation
Solved: No attempts yet

Problem

The painter Quasimir Malevich painted a picture called "Black-and-white square". The picture is a rectangle filled with black cells and white cells.

Art historian Erik Stripeson proposed a hypothesis about how Malevich painted it. The canvas was white at the start, and the painter drew black stripes one cell wide, each running from one edge of the canvas to the opposite edge, either horizontally or vertically.

The Association of Computational Art Studies wants to find out whether this hypothesis can be correct. If it can be correct, the association also wants the minimal number of stripes needed to paint the picture, and a way to paint it with that many stripes.

Input

The first line contains the height $h$ and the width $w$ of the picture ( $1 \le h, w \le 50$ ).

Each of the next $h$ lines contains $w$ numbers separated by spaces. The number 0 is a white cell and the number 1 is a black cell.

Output

If the hypothesis cannot be correct, print only -1.

If the hypothesis can be correct, print on the first line the minimal number of stripes $n$ .

On the second line print $n$ numbers in increasing order, separated by spaces, describing a way to paint the picture. A positive number $x$ means drawing a vertical stripe in column $x$ (columns are numbered from the left, starting with 1), and a negative number $-x$ means drawing a horizontal stripe in row $x$ (rows are numbered from the top, starting with 1).

If several sets of $n$ stripes paint the picture, print the one whose increasing sequence is smallest in lexicographic order. When $n$ is 0, the second line is empty.

Examples4

Example 1
Input
```
3 4
1 0 1 0
1 1 1 1
1 1 1 1
```
Expected output
```
4
-3 -2 1 3
```
Example 2
Input
```
2 2
1 0
0 0
```
Expected output
```
-1
```
Example 3
Input
```
1 1
0
```
Expected output
```
0
```
Example 4
Input
```
1 1
1
```
Expected output
```
1
-1
```