0084 - 迷路の問題だよ！

問題

あるH高校にMr.fourがいました。
Mr.fourは「ラヲライブ ロリコンオメガフェスティバル」が大好きです。このゲームはある迷路を早くクリアするゲームです。Mr.fourはプライドが高いので、なんとしても4位を取りたいそうです。なので、迷路を最短で進む必要があるようです。しかし、Mr.fourは頭が悪いのです。( 数学４((以下略 )
頭のいいみんながMr.fourを救ってあげよう!!!

課題

N×Mの迷路の地図が与えられる。迷路は各マスごとに状態がある。その状態は4つある。

• '#' : 壁
• '.' : 通路
• 'S' : スタート
• 'G' : ゴール

迷路は通路と壁からできていて、1ターンに隣接する上下左右4マスの通路へ移動することができる。スタートからゴールまで移動するのに必要な最小のターン数を求めなさい。ただし、必ずスタートからゴールまで移動できるものとする。

入力

N M
a1,1 a2,1 ... aN,1
a1,2 a2,2 ... aN,2
   :
   :
   :
a1,M a1,M ... aN,M

出力

迷路のスタートからゴールまで移動するのに必要な最小のターン数を出力する。

sample

input

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

output

4