問題文

縦 $H$ マス、横 $W$ マスの $2$ 次元グリッドで表された街があります。
上から $i$ 行目、左から $j$ 列目のマスの情報が文字 $a_{i,j}$ により与えられます。 $a_{i,j}$ は S , G , . , # , a ~ z のいずれかです。
# は入ることができないマスを、a ~ z はテレポーターのあるマスを表します。

高橋くんははじめ S のマスにおり、 $1$ 秒ごとに以下のいずれかの移動を行います。

• 現在いるマスと上下左右に隣り合う、# でないマスに移動する。
• 今いるマスと同じ文字が書かれているマスを $1$ つ選び、そこにテレポートする。この移動は現在いるマスが a ~ z のいずれかであるとき使える。

高橋くんが S のマスから G のマスに移動するのに必要な最短の時間を求めてください。
ただし、どうしても G のマスにたどり着けない場合は、代わりに -1 を出力してください。

制約

• $1 \\le H, W \\le 2000$
• $a_{i,j}$ は S , G , . , # , 英小文字のいずれか
• S のマスと G のマスはちょうど $1$ つ存在する

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $a_{1,1}\\dots a_{1,W}$ $\\vdots$ $a_{H,1}\\dots a_{H,W}$

出力

S のマスから G のマスに移動するのに必要な最短時間を出力せよ。
S のマスから G のマスに移動する方法が存在しない場合は、代わりに -1 を出力せよ。

入力例 1

2 5
S.b.b
a.a.G

出力例 1

4

上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ で表すこととします。
はじめ、高橋くんは $(1, 1)$ にいます。 例えば、以下のような手順で $4$ 秒で $(2, 5)$ に移動することができます。

• $(1, 1)$ から $(2, 1)$ に移動する
• $(2, 1)$ と同じ a のマスである $(2, 3)$ にテレポートする
• $(2, 3)$ から $(2, 4)$ に移動する
• $(2, 4)$ から $(2, 5)$ に移動する

入力例 2

11 11
S##...#c...
...#d.#.#..
..........#
.#....#...#
#.....bc...
#.##......#
.......c..#
..#........
a..........
d..#...a...
.#........G

出力例 2

14

入力例 3

11 11
.#.#.e#a...
.b..##..#..
#....#.#..#
.#dd..#..#.
....#...#e.
c#.#a....#.
.....#..#.e
.#....#b.#.
.#...#..#..
......#c#G.
#..S...#...

出力例 3

-1