치즈

N×M 모눈종이에 매우 얇은 치즈가 놓여 있다. N은 세로 칸의 수, M은 가로 칸의 수이다. 이 치즈를 실내 온도에 두면 공기와 닿은 부분부터 천천히 녹는다. 각 치즈 칸은 네 변 중에서 두 변 이상이 외부 공기와 맞닿아 있으면 정확히 1시간 뒤에 녹아 사라진다. 따라서 아래 그림 1에서 C로 표시된 치즈 칸들은 1시간 뒤에 모두 사라진다.

그림 1

치즈 내부에 갇힌 빈 공간은 외부 공기와 접촉하지 않는 것으로 본다. 그래서 그림 2처럼 내부 공간에만 맞닿은 치즈 칸은 녹지 않고, C로 표시된 치즈 칸만 사라진다. 하지만 시간이 지나 내부 공간이 외부와 연결되면 그 공간도 외부 공기가 되어, 그림 3처럼 새롭게 C로 표시된 치즈 칸들이 다음에 사라진다.

그림 2

그림 3

모눈종이의 가장자리에는 치즈가 놓이지 않는다. 입력으로 주어진 치즈가 모두 녹아 없어지는 데 걸리는 정확한 시간을 구하시오.

첫째 줄에 모눈종이의 크기를 나타내는 두 정수 N, M이 주어진다. (5 ≤ N, M ≤ 100)

다음 N개 줄에는 모눈종이의 각 칸 상태가 주어진다. 치즈가 있는 칸은 1, 치즈가 없는 칸은 0으로 표시되며, 각 값은 공백으로 구분된다.

주어진 치즈가 모두 녹아 없어지는 데 걸리는 정확한 시간을 정수로 출력한다.