직사각형 모양의 공간에 여러 개의 전등이 있다. 각 칸은 벽, 불이 꺼진 칸, 불이 켜진 칸 중 하나이다.

매일 불이 켜진 모든 칸은 상하좌우로 인접한 불이 꺼진 칸을 동시에 밝힌다. 벽에는 불이 퍼질 수 없다.

모든 칸을 밝히는 데 며칠이 걸리는지 구해 보자. 여기서 벽은 밝힐 필요가 없다.

입력

첫째 줄에 공간의 세로 크기 \(H\)와 가로 크기 \(W\)가 공백으로 구분되어 주어진다.

다음 \(H\)개의 줄에 각 칸의 상태가 공백으로 구분되어 주어진다.

• -1은 벽이다.
• 0은 불이 꺼진 칸이다.
• 1은 처음부터 불이 켜진 칸이다.

출력

모든 불이 꺼진 칸을 밝히는 데 필요한 최소 일수를 출력한다.

처음부터 밝힐 칸이 없다면 0을 출력한다. 밝힐 수 없는 칸이 하나라도 있다면 -1을 출력한다.

제한

• \(1 \le H,W\)
• \(H \times W \le 1,000\)
• 처음부터 불이 켜진 칸이 하나 이상 존재한다.

예제 입력 1

3 5
1 0 0 -1 0
0 0 0 -1 1
0 -1 0 0 0

예제 출력 1

3

예제 입력 2

3 4
1 -1 0 0
-1 -1 -1 -1
0 0 0 1

예제 출력 2

-1