题目描述

Takahashi has a maze, which is a grid of $H \times W$ squares with $H$ horizontal rows and $W$ vertical columns.

The square at the $i$-th row from the top and the $j$-th column is a "wall" square if $S_{ij}$ is #, and a "road" square if $S_{ij}$ is ..

From a road square, you can move to a horizontally or vertically adjacent road square.

You cannot move out of the maze, move to a wall square, or move diagonally.

Takahashi will choose a starting square and a goal square, which can be any road squares, and give the maze to Aoki.

Aoki will then travel from the starting square to the goal square, in the minimum number of moves required.

In this situation, find the maximum possible number of moves Aoki has to make.

高桥有一个迷宫，它是由 $H \times W$ 个方格组成的网格，其中横向有 $H$ 行，纵向有 $W$ 列。

如果 $S_{ij}$ 为 "#"，那么位于从上往下第 $i$ 行和第 $j$ 列的方格是 "墙 "方格；如果 $S_{ij}$ 为"."，那么位于从上往下第 $i$ 行和第 $j$ 列的方格是 "路 "方格。

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

您不能移动出迷宫、移动到墙壁方格或斜向移动。

高桥将选择一个起始方格和一个目标方格（可以是任何道路方格），然后把迷宫交给青木。

青木将以最少的移动次数从起点方格到达目标方格。

在这种情况下，请找出青木需要走的最大步数。

输入格式

输入内容按以下格式标准输入：

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

输出格式

打印青木要走的最大步数。

样例 #1

样例输入 #1

3 3
...  
...  
...  

样例输出 #1

4

样例 #2

样例输入 #2

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

样例输出 #2

10

说明

数据规模与约定

• $1 \leq H,W \leq 20$
• $S_{ij}$ 是 . 或 #。
• $S$ 至少包含两个 .。
• 任何道路方格都可以在零步或更多步内从任何道路方格到达。

样例 $1$ 解释

如果高桥选择左上方的位置作为起始位置，右下方的位置作为目标位置，那么青木必须下四步棋。

样例 $2$ 解释

如果高桥选择左下方的位置作为起始位置，右上方的位置作为目标位置，那么青木需要下十步棋。