题目描述

给定一个有$H$行$W$列的方格网格，每个方格被涂上白色或黑色。用$HW$个字符$A_{11}$到$A_{HW}$表示方格的颜色。如果位于从上方以及从左侧数第$i$行、第$j$列的方格是黑色，则$A_{ij}$为#；如果方格是白色，则$A_{ij}$为.。

我们将反复执行以下操作，直到所有方格都变为黑色：

• 与至少一个黑色方格共享边的每个白色方格都会变为黑色。

找出执行的操作次数。初始方格至少有一个黑色方格。

约束条件

• $1 \leq H, W \leq 1000$
• $A_{ij}$ 是 # 或 .。
• 给定方格至少有一个黑色方格。

输入

输入以以下格式从标准输入给出：

$H$ $W$ $A_{11}$$A_{12}$$...$$A_{1W}$ $:$ $A_{H1}$$A_{H2}$$...$$A_{HW}$

输出

打印执行的操作次数。

示例输入1

3 3
...
.#.
...

示例输出1

2

经过一次操作后，除了角落的方格外，其它所有方格都变为黑色。再经过一次操作，所有方格都变为黑色。

示例输入2

6 6
..#..#
......
#..#..
......
.#....
....#.

示例输出2

3