흑백 사각형

면접 대비

시간 제한1초메모리 제한256 MB

요약

검은 칸이 몇 개의 전체 행과 열의 합집합과 일치하는지 판정하고 가장 작은 줄무늬 집합을 출력합니다.

난이도: 보통10점 중 5점
유형: 행렬, 구현
정답자: 아직 제출이 없습니다

문제

화가 Quasimir Malevich는 "흑백 사각형"이라는 그림을 그렸다. 이 그림은 검은 칸과 흰 칸으로 채워진 직사각형이다.

미술사학자 Erik Stripeson은 Malevich가 다음과 같은 방법으로 그림을 그렸다는 가설을 내놓았다. 처음 캔버스는 전부 희었고, 화가는 폭이 한 칸인 검은 줄을 캔버스의 한쪽 끝에서 반대쪽 끝까지 가로 방향 또는 세로 방향으로 그었다.

계산예술연구협회는 이 가설이 맞을 수 있는지 알아내려 한다. 맞을 수 있다면 그림을 그리는 데 필요한 줄의 최소 개수와, 그 개수로 그림을 그리는 방법도 알고 싶어 한다.

입력

첫째 줄에 그림의 높이 $h$ 와 너비 $w$ 가 주어진다 ( $1 \le h, w \le 50$ ).

다음 $h$ 개 줄에는 각각 공백으로 구분된 $w$ 개의 수가 주어진다. 0은 흰 칸, 1은 검은 칸이다.

출력

가설이 맞을 수 없으면 -1만 출력한다.

가설이 맞을 수 있으면 첫째 줄에 필요한 줄의 최소 개수 $n$ 을 출력한다.

둘째 줄에는 그림을 그리는 방법을 나타내는 $n$ 개의 수를 증가하는 순서로, 공백으로 구분해 출력한다. 양수 $x$ 는 $x$ 번째 열에 세로 줄을 긋는다는 뜻이고 (열은 왼쪽부터 1번), 음수 $-x$ 는 $x$ 번째 행에 가로 줄을 긋는다는 뜻이다 (행은 위쪽부터 1번).

크기가 $n$ 인 줄의 집합이 여러 개이면, 증가하는 순서로 나열했을 때 사전순으로 가장 앞서는 것을 출력한다. $n$ 이 0이면 둘째 줄은 비어 있다.

예제4

예제 1
입력
```
3 4
1 0 1 0
1 1 1 1
1 1 1 1
```
예상 출력
```
4
-3 -2 1 3
```
예제 2
입력
```
2 2
1 0
0 0
```
예상 출력
```
-1
```
예제 3
입력
```
1 1
0
```
예상 출력
```
0
```
예제 4
입력
```
1 1
1
```
예상 출력
```
1
-1
```