题目描述

给定一个 $n \times m$ 的二元矩阵，其中 $1$ 代表黑色单元格，$0$ 代表白色单元格。每一秒，每个黑色单元格会将其上、下、左、右四个相邻的白色单元格变为黑色。你可以将最多一个白色单元格变为黑色（将 $0$ 变为 $1$），以最小化整个矩阵完全变黑所需的时间。求出这个最短时间。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n \times m \leq 2 \times 10^5)$，表示矩阵的行数和列数。

接下来的 $n$ 行，每行包含 $m$ 个数字（$0$ 或 $1$），表示矩阵的初始状态。

输出格式

输出一个整数，表示在增加一个黑色单元格后，使整个矩阵变黑所需的最短时间。

输入输出样例 #1

输入 #1

3 3
0 0 0
0 0 0
0 0 1

输出 #1

2

输入输出样例 #2

输入 #2

2 2
1 0
0 0

输出 #2

1

输入输出样例 #3

输入 #3

1 5
0 1 0 0 0

输出 #3

1