有一个由 H 行 W 列的方格组成的迷宫。记从上数第 i 行、从左数第 j 列的格子为 (i,j)。格子 (i,j) 的类型由字符 S_{i,j} 给出，各字符含义如下：

- `.`：空地

- `#`：障碍物

- 小写英文字母（`a`-`z`）：传送点

在迷宫中，可以按任意顺序、任意次数进行以下两种行动：

- 步行：从当前格子移动到上下左右四个方向中某个方向上相邻 1 格的格子。但是，不能移动到障碍物格子或迷宫外部。

- 传送：处于传送点时，可以移动到写着相同字母的任意一个传送点。

判断能否从格子 (1,1) 移动到格子 (H,W)，如果可以，求出所需的最小总行动次数。

输入按以下格式给出：

```

H W

S_{1,1}S_{1,2}...S_{1,W}

...

S_{H,1}S_{H,2}...S_{H,W}

```

如果可以从 (1,1) 移动到 (H,W)，输出所需的最小总行动次数；否则输出 `-1`。

样例1说明：

例如按如下方式行动，可以从 (1,1) 移动到 (3,4)：

1. 从 (1,1) 步行到 (1,2)。

2. 从 (1,2) 步行到 (1,3)。

3. 从 (1,3) 传送到 (3,2)。

4. 从 (3,2) 步行到 (3,1)。

5. 从 (3,1) 传送到 (3,4)。

总行动次数为 5，这是最小值。

n,m\leq 1000