토마토

철수의 토마토 농장에는 토마토를 보관하는 큰 창고가 있다. 토마토는 아래 그림처럼 격자 모양 상자의 각 칸에 하나씩 넣은 뒤, 상자들을 수직으로 쌓아 올려 창고에 보관한다.

창고에 보관된 토마토 중에는 이미 잘 익은 것도 있고, 아직 익지 않은 것도 있다. 보관한 지 하루가 지나면 익은 토마토와 인접한 곳에 있는 익지 않은 토마토들이 익은 토마토의 영향을 받아 함께 익는다. 어떤 토마토와 인접한 칸이란 위, 아래, 왼쪽, 오른쪽, 앞, 뒤의 여섯 방향에 맞닿아 있는 칸을 뜻한다. 대각선 방향의 토마토에는 영향을 주지 않으며, 토마토가 저절로 익는 일은 없다고 가정한다.

격자 상자의 크기와 익은 토마토·익지 않은 토마토의 정보가 주어질 때, 보관된 토마토가 모두 익기까지 걸리는 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어 있지 않을 수도 있다.

첫째 줄에 상자의 크기를 나타내는 두 정수 $M$, $N$과 쌓아 올린 상자의 수 $H$가 주어진다. $M$은 상자의 가로 칸 수, $N$은 세로 칸 수이다. 단, $2 \le M \le 100$, $2 \le N \le 100$, $1 \le H \le 100$이다.

둘째 줄부터는 가장 아래 상자부터 가장 위 상자까지 저장된 토마토의 정보가 주어진다. 즉, 하나의 상자는 $N$개의 줄로 표현되며, 각 줄에는 그 가로줄에 들어 있는 토마토의 상태가 $M$개의 정수로 주어진다. 정수 $1$은 익은 토마토, $0$은 익지 않은 토마토, $-1$은 토마토가 들어 있지 않은 칸을 나타낸다. 이렇게 $N$개의 줄로 이루어진 상자 정보가 아래에서 위로 $H$번 반복되어 주어진다.

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

토마토가 모두 익을 때까지 걸리는 최소 일수를 출력한다. 만약 저장할 때부터 모든 토마토가 이미 익어 있다면 $0$을 출력하고, 토마토가 모두 익지는 못하는 상황이라면 $-1$을 출력한다.