题目描述

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

如果第$i$行从上往下，第$j$列从左往右的方块是“墙“方块，那么$S_{ij}$等于#，如果是“道路”方块，那么$S_{ij}$等于.。

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

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

Takahashi将选择一个起始方块和一个目标方块，它们可以是任何道路方块，并将迷宫交给Aoki。

然后，Aoki将从起始方块出发，走到目标方块，要求走的步数最少。

在这种情况下，求出Aoki最多需要走的步数。

输入

第一行是两个整数，表示迷宫的高$n$和宽$m$

接下来是一个是一个$n \times m$的字符矩形，表示迷宫

输出

输出Aoki最多需要走的步数。

3 3
...
...
...

4

样例解释

akahashi选择左上方的方块作为起始方块，将右下方的方块作为目标方块，Aoki最多需要走4步。

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

10

样例解释

Takahashi选择左下方的方块作为起始方块，将右上方的方块作为目标方块，Aoki最多需要走10步。

提示

• $1\ \leq\ H,W\ \leq\ 20$
• $s_{ij} 中只包含$ .或#