You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目内容

塔子哥最近开始研究了植物病毒学，他发现了一种名为 $X$ 的超级病毒，该病毒在农作物间的传染性极强。现有一块 $N$ 行 $M$ 列的农田，每一个格子都栽种着一株植物，每株植物只有感染了病毒和未感染病毒两种状态，假定已经感染病毒的植物用 $0$ 表示，未感染的植物用 $1$ 表示。

塔子哥需要使这块农田里所有植物都感染上病毒，以获得更多的实验材料。已知塔子哥一次操作只能让一株植物感染上病毒，当这一株未感染病毒的植物感染了 $X$ 病毒，那么与它相邻的上、下、左、右、左上、左下、右上、右下这八个方向的未感染植物都会发生感染，进一步地，当一个原本未感染的植物发生感染后，与其相邻的$8$个方向上的未感染植物均会发生感染。

给定一个样例如下：

1 0 1
0 1 0
1 0 1

按照上述规则，塔子哥最少需要操作 $1$ 次后，所有的植物都会感染X病毒。

请问，给定一个由 $0$ 和 $1$ 组成的农田矩阵，塔子哥最少需要操作几次后，农田里所有植物都会感染上 $X$ 病毒。

输入描述

第一行输入两个数字 $N$ , $M$ $(1 \leq N,M \leq 1000)$，分别表示二维矩阵的行数，列数，并用空格隔开

下面输入 $N$ 行，每行 $M$ 个数字，并用空格隔开

输出描述

最少需要点击几次后，矩阵中所有数字均为 $0$ 。

样例

输入

3 3
1 0 1
0 1 0
1 0 1

输出

1