该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

吕某有一个由 $H$ 行 $W$ 列组成的 $H \times W$ 格子的迷宫。

第 $i$ 行第 $j$ 列的格子 $(i,j)$，当 $S_{ij}$ 为 # 时表示墙壁，为 . 时表示道路。

移动的条件是：

• 从道路格子可以移动到上下左右相邻的道路格子。
• 不能移动到迷宫外部、墙壁格子，也不能斜向移动。

吕某可以自由选择一个道路格子作为起点和终点，然后把迷宫交给黄某。

黄某会以最少的移动次数从起点移动到终点。

请问，吕某如何选择起点和终点，使得黄某的最小移动次数最大？输出这个最大值。

输入格式

输入从标准输入按以下格式给出。

$H$ $W$
$S_{11} \ldots S_{1W}$
$\vdots$
$S_{H1} \ldots S_{HW}$

其中：

• $1 \leq H, W \leq 20$
• $S_{ij}$ 只包含 . 或 #
• $S$ 至少包含两个 .（即至少有两个道路格子）
• 任意两个道路格子之间都可以通过 $0$ 次或多次移动到达

输出格式

输出黄某的最小移动次数的最大值。

样例

3 3
...
...
...

4

样例解释 1

如果吕某选择左上角格子为起点，右下角格子为终点，黄某的移动次数为 $4$。

3 5
...#.
.#.#.
.#...

10

样例解释 2

如果吕某选择左下角格子为起点，右上角格子为终点，黄某的移动次数为 $10$。