問題文

縦 $H$ 行、横 $W$ 列のグリッドがあります。 上から $i$ 行目、左から $j$ 列目のマスを $( i,\space j ) $で表します。 グリッドは . 、 # 、 S 、 Gから成り、. は通路マス、 # は壁マス、 S はスタートマス、 G はゴールマスを表します。ここで、マス $(1, \space 1)$ は S 、マス $(H, \space W)$ は G であり、それ以外に S 、 G のマスはありません。

あなたはスタート前に以下の2種類の超能力をそれぞれ0回以上使用することができます。

• 隣り合う2行を選び、その間に . の行を挿入する。
• 隣り合う2列を選び、その間に . の列を挿入する。

例えばグリッドが

S . # 
. # # 
. # G 

である時に超能力を2行目と3行目の間に使用するとグリッドは以下のように変化します。

S . # 
. # # 
. . . 
. # G 

ここにさらに超能力を1列目と2列目の間に使用するとグリッドは以下のように変化します。

S . . #
. . # #
. . . .
. . # G

あなたは、現在いるマスと上下左右に隣りあうマスに移動することができます。 ただし、グリッドの範囲外や壁マスに移動することはできません。

超能力を使用した後のマス目において、Sから G に到達できるかどうか判定し、もし到達できるなら移動する回数の最小値を求めてください。

制約

• $2 \le H \le 2 \times 10^3$
• $2 \le W \le 2 \times 10^3$
• $H,W$ は整数
• $C_{i,j}$ は.,#,S,Gのいずれかである
• S は $(1, \space 1)$ , G は $(H, \space W)$ の一箇所ずつのみである

入力

$H\ W$
$C_{1,1}\ C_{1,2}\ \ldots \ C_{1,W}$
$C_{2,1}\ C_{2,2}\ \ldots \ C_{2,W}$
$\vdots$
$C_{H,1}\ C_{H,2}\ \ldots \ C_{H,W}$

出力

到達可能である場合は移動回数の最小値を、そうでない場合は−1を出力してください。

サンプル

3 3
S.#
.##
.#G

5

2 2
S.
.G

2

5 4
S...
###.
....
.###
...G

8