题目描述

Takahashi 有一个迷宫，它是一个 $H \\times W$ 的方格，其中 $H$ 是水平行数，$W$ 是垂直列数。

如果第 $i$ 行第 $j$ 列的方格是 #，则表示这个方格是一个 "墙" 方格；如果是 .，则表示这个方格是一个 "路" 方格。

从一个路方格可以移动到水平或垂直相邻的路方格。

你不能移出迷宫，也不能移动到墙方格，或者对角线移动。

Takahashi 将选择一个起始方格和一个目标方格，两者都可以是任意的路方格，并将迷宫交给 Aoki。

然后，Aoki 将从起始方格移动到目标方格，需要的最少步数。

在这种情况下，找出 Aoki 需要移动的最大可能步数。

约束条件

• $1 \\leq H,W \\leq 20$
• $S_{ij}$ 是 . 或 #
• $S$ 中至少包含两个 . 出现
• 从任何一个路方格都可以通过零个或多个移动到达任何一个路方格。

输入

从标准输入读入数据，格式如下：

$H$ $W$ $S_{11}$$...$$S_{1W}$ $:$ $S_{H1}$$...$$S_{HW}$

输出

打印出 Aoki 需要移动的最大可能步数。

示例输入 1

3 3
...
...
...

示例输出 1

4

如果 Takahashi 将左上角方格作为起始方格，将右下角方格作为目标方格，Aoki 需要移动四步。

示例输入 2

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

示例输出 2

10

如果 Takahashi 将左下角方格作为起始方格，将右上角方格作为目标方格，Aoki 需要移动十步。