Square Painting

問題文

　縦横 $H \times W$ のグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と表します。 各マスの状態は $S_{i,j}$ で表されます。各マスの状態は次の $4$ つのいずれかです。

• S:スタート地点。グリッド上にちょうど $1$ つだけ存在する。
• G:ゴール地点。グリッド上にちょうど $1$ つだけ存在する。
• .:白色で塗られたマス。
• #:黒色で塗られたマス。

　yura君はスタート地点を出発してグリッド上を移動してゴール地点へ行こうとしています。yura君は $(i, j)$ にいるときにマス $(i+1, j), (i, j+1), (i-1, j), (i, j-1)$ のいずれかに移動することが出来ます。 ただし、グリッドの外に出るような移動や、黒で塗られたマスへの移動を行うことは出来ません。
お金持ちのyura君は、移動中に次の行動を何度でも行うことが出来ます。

• $N$ 円を支払い、好きな $N\times N$ の領域を選びすべて白で塗る。

　yura君がスタート地点からゴール地点へ到達するために必要な最小の金額を求めてください。

制約

• $2 \le H, W \le 1000$
• $H, W$ は整数
• $S_i$ は S, G, ., # からなる長さ $W$ の文字列
• S, G は $S_{i, j}$ の中でちょうど $1$ 回だけ登場する．

入力

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

出力

　yura君がゴールするのに必要な最小の金額を $1$ 行に出力してください。

入力例1

3 3
S##
.#.
##G

出力例1

1

　$(2, 2)$ を白く塗ることで、$1$ 円でゴールすることが出来ます。

入力例2

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

出力例2

0

　$1$ 円も支払うことなくゴールすることが出来ます。

入力例3

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

出力例3

3