题目描述

强哥设计了一个有趣的探险地图，地图由 $H$ 行 $W$ 列组成，总共 $H \times W$ 个格子。

每个格子 $(i,j)$ 有两种类型：

• 如果是 #，表示这里是一座小山，探险者无法通过；
• 如果是 .，表示这里是平坦的道路，探险者可以通过。

探险者只能在道路格子之间移动，每次可以向上、下、左、右四个方向中的一个方向走一步，到达相邻的格子。但不能走到地图外面、不能穿越小山，也不能斜着走。

强哥可以任意选择一个道路格子作为探险的起点，再任意选择一个道路格子作为终点，然后把地图交给探险队。

探险队会采用最少的步数从起点走到终点。

强哥希望设计一个最有挑战性的路线，使得探险队必须走尽可能多的步数才能完成。

请问：强哥应当如何选择起点和终点，才能让探险队的最少步数达到最大？输出这个最大的步数。

输入格式

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

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

输出格式

输出探险队所需的最少步数的最大值。

输入输出样例 #1

输入 #1

3 3
...
...
...

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

10

说明/提示

限制条件

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

样例解释 1

如果强哥选择左上角格子为起点，右下角格子为终点，探险队的最少步数为 $4$。

样例解释 2

如果强哥选择左下角格子为起点，右上角格子为终点，探险队的最少步数为 $10$。