問題文

オシャレ好きのビ太郎は，カーペットを新調した．カーペットは縦 $H$ 行，横 $W$ 列のマス目状に区切られた長方形の形をしており，各マスは白か黒のいずれかの色で塗られている．カーペットの上から $i$ 行目，左から $j$ 列目 ($1 \le i \le H$，$1 \le j \le W$) にあるマスの色は，文字列 $S_i$ の $j$ 文字目が . のとき白色，# のとき黒色である．

ビ太郎は，カーペットの最も左上のマスに駒を置き，以下の操作を何回か行うことで，その駒をカーペットの最も右下のマスに到達させるという遊びを思いついた．

• 駒が置かれているマスと色が異なり，かつ上下左右に隣接するマスを $1$ つ選び，そのマスに駒を移動させる．

ビ太郎は，到達までの操作回数をなるべく少なくしたい．ただし，カーペットの模様によっては到達させられないかもしれない．

カーペットの模様の情報が与えられたとき，操作を繰り返すことで左上のマスから右下のマスに駒を到達させることが可能かを判定し，可能ならば操作回数の最小値を求めるプログラムを作成せよ．

制約

• $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$ の制約を満たす．