토마토

창고에 토마토를 격자 모양 상자에 한 칸당 하나씩 넣어 보관한다. 격자의 각 칸에는 익은 토마토, 익지 않은 토마토가 있거나, 토마토가 아예 없을 수 있다.

하루가 지날 때마다, 익은 토마토와 상·하·좌·우로 인접한 익지 않은 토마토가 익는다. 대각선 방향으로는 영향을 주지 못하며, 토마토가 저절로 익는 일은 없다.

격자의 크기와 각 칸의 초기 상태가 주어졌을 때, 모든 토마토가 익기까지 걸리는 최소 일수를 구하라. 단, 일부 칸에는 토마토가 없을 수도 있다.

첫째 줄에 상자의 크기를 나타내는 두 정수 $M$과 $N$이 주어진다. $M$은 가로 칸의 수, $N$은 세로 칸의 수이며 $2 \le M, N \le 1{,}000$ 이다.

둘째 줄부터 $N$개의 줄에 걸쳐 상자의 상태가 주어진다. 각 줄에는 가로 한 줄에 들어 있는 $M$개의 정수가 주어지며, $1$은 익은 토마토, $0$은 익지 않은 토마토, $-1$은 토마토가 없는 칸을 나타낸다.

토마토가 하나 이상 있는 경우만 입력으로 주어진다.

모든 토마토가 익을 때까지의 최소 일수를 출력한다. 저장할 때부터 모든 토마토가 이미 익어 있으면 $0$을, 모든 토마토가 끝내 익지 못하면 $-1$을 출력한다.