题目描述

热爱时尚的 Bitaro 新买了一块地毯。地毯呈长方形，被划分为纵 $H$ 行、横 $W$ 列的网格状，每个格子被涂成白色或黑色之一。地毯从上往下第 $i$ 行、从左往右第 $j$ 列（$1 \le i \le H$，$1 \le j \le W$）的格子的颜色，在字符串 $S_i$ 的第 $j$ 个字符为 . 时是白色，为 # 时是黑色。

Bitaro 想出了一个游戏：在地毯最左上角的格子上放一枚棋子，通过若干次以下操作，使该棋子到达地毯最右下角的格子。

• 选择 $1$ 个与棋子当前所在格子颜色不同、且上下左右相邻的格子，将棋子移动到该格子上。

Bitaro 希望到达终点所需的操作次数尽可能少。不过，根据地毯图案的不同，也有可能无法到达。

给定地毯图案的信息，请编写程序，判断通过重复操作是否能使棋子从左上角的格子到达右下角的格子；如果可能，求出操作次数的最小值。

数据范围

• $1 \le H \le 500$。
• $1 \le W \le 500$。
• $(H, W) \neq (1, 1)$。
• $S_i$ 是长度为 $W$ 的字符串（$1 \le i \le H$）。
• $S_i$ 的每个字符是 . 或 #（$1 \le i \le H$）。
• $H, W$ 是整数。

子任务

1. （$4$ 分）$H = 1$。
2. （$14$ 分）$H \le 5$，$W \le 5$。
3. （$24$ 分）$H \le 30$，$W \le 30$。
4. （$58$ 分）无额外限制。

输入格式

输入从标准输入按以下格式给出：

H W
S_1
S_2
:
S_H

输出格式

如果通过重复操作能使棋子从左上角的格子到达右下角的格子，则输出操作次数的最小值；如果不可能，则输出 -1。向标准输出在 $1$ 行内输出。

样例

样例输入 1

4 5
...#.
#####
...#.
#.###

样例输出 1

9

例如，可以考虑如图所示的操作。

在左边的例子中通过 $9$ 次操作、在右边的例子中通过 $13$ 次操作，都可以使棋子从左上角的格子到达右下角的格子。

因为不可能用少于 $9$ 次的操作到达，所以输出 $9$。

该样例输入满足子任务 $2, 3, 4$ 的限制。

样例输入 2

3 3
...
...
...

样例输出 2

-1

也存在从一开始就无法进行操作的情况。在这种情况下，因为不可能使棋子到达右下角的格子，所以输出 -1。

该样例输入满足子任务 $2, 3, 4$ 的限制。

样例输入 3

1 5
.#.#.

样例输出 3

4

该样例输入满足所有子任务的限制。

样例输入 4

5 5
###.#
.#...
.#..#
.####
##..#

样例输出 4

12

该样例输入满足子任务 $2, 3, 4$ 的限制。

样例输入 5

7 5
.#.##
##...
.#.##
.###.
##.#.
...#.
##.#.

样例输出 5

12

该样例输入满足子任务 $3, 4$ 的限制。