섬의 침식

세로로 N칸, 가로로 M칸인 격자 모양의 해도가 있다. 각 칸에는 땅이면 1, 바다면 0이 적혀 있다. 해도의 가장자리에 해당하는 칸은 모두 바다다.

이 해도의 땅은 바닷물에 깎여 나간다. 한 해가 지날 때마다 다음과 같은 일이 한꺼번에 일어난다. 어떤 땅 칸이 가로와 세로로 맞닿은 네 칸 가운데 바깥 바다인 칸과 두 칸 이상 닿아 있으면, 그 땅 칸은 한 해 뒤에 깎여 바다가 된다. 네 칸 가운데 바깥 바다인 칸이 하나뿐이거나 아예 없으면 그 땅 칸은 그 해에는 남는다. 대각선으로 맞닿은 칸은 세지 않는다.

이때 바깥 바다는 해도의 가장자리에서 출발해 바다 칸만 밟고 걸어서 닿을 수 있는 바다를 말한다. 땅으로 둘러싸여 바깥과 끊어진 바다는 호수이며, 호수와 닿은 면은 세지 않는다.

결과적으로 처음의 해도가 주어졌을 때, 땅이 모두 깎여 없어지기까지 몇 해가 걸리는지 구하는 프로그램을 작성하여라.

예를 들어 N=5, M=5이고 해도가 다음의 표와 같다고 해보자.

위쪽 땅 칸은 위, 왼쪽, 오른쪽의 세 면이 바깥 바다와 닿아 있고, 아래쪽 땅 칸은 아래, 왼쪽, 오른쪽의 세 면이 바깥 바다와 닿아 있다. 둘 다 두 면 이상이므로 한 해 뒤에 함께 깎여 사라진다. 따라서 이 경우 정답은 1이다.

호수가 있는 경우도 살펴보자. N=7, M=7이고 땅이 가운데를 둘러싸는 고리 모양으로 놓여 있다고 해보자.

고리 가운데의 아홉 칸은 바다이지만 땅에 막혀 바깥과 끊어져 있으므로 호수다. 고리의 네 귀퉁이는 바깥 바다와 두 면이 닿아 있어 첫 해에 깎인다. 반면에 귀퉁이가 아닌 칸들은 바깥 바다와 한 면만 닿고 나머지 한 면은 호수와 닿으므로 첫 해에는 남는다. 두 번째 해에는 귀퉁이가 사라진 자리가 바깥 바다가 되어 그 옆 칸들이 두 면씩 닿게 되므로 함께 깎인다. 세 번째 해에는 남은 네 칸이 모두 깎인다. 따라서 이 경우 정답은 3이다.

입출력 예시

예시 1

입력

5 5
0 0 0 0 0
0 0 0 1 0
0 0 0 1 0
0 0 0 0 0
0 0 0 0 0

출력

1

예시 2

입력

3 3
0 0 0
0 0 0
0 0 0

출력

0

예시 3

입력

8 9
0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 0 0
0 0 0 1 1 0 1 1 0
0 0 1 1 1 1 1 1 0
0 0 1 1 1 1 1 0 0
0 0 1 1 0 1 1 0 0
0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 0 0 0

출력

4