题目描述

希蒙有一个由 H 行 W 列组成的迷宫。

迷宫中的每个单元格 $(i, j)$，如果 $S_{ij}$ 是 #，表示墙；如果 $S_{ij}$ 是 .，表示道路。

你可以从一个有道路的单元格移动到上下左右相邻的有道路的单元格。

你不能走出迷宫、走到墙上的单元格，也不能进行斜对角移动。

希蒙可以自由选择道路上的起点和终点，然后将迷宫交给蒙蒙。

蒙蒙将以最小移动次数的方式从起点移动到终点。

当希蒙选择适当的起点和终点时，蒙蒙的最大移动次数是多少？

输入格式

第一行输入两个整型变量 H 、 W 接下来 H 行 W 列输入迷宫。

输出格式

输出蒙蒙移动次数的最大值。

样例 #1

样例输入 #1

3 3
...
...
...

样例输出 #1

4

样例 #2

样例输入 #2

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

样例输出 #2

10

提示

制約

• $1\ \leq\ H,W\ \leq\ 20$
• $S_{ij}$ 只能是 . 或 #
• $S$ 中至少有两个 .（空地）
• 你可以在零次或更多次移动中从任意有道路的单元格到达另一个有道路的单元格。

样例解释 1

当希蒙选择左上角的单元格作为起点，右下角的单元格作为终点时，蒙蒙的移动次数将为 4。

样例解释 2

当希蒙选择左下角的单元格作为起点，右上角的单元格作为终点时，蒙蒙的移动次数将为 10。