AT_oidashi_a 不完全迷路

[problemUrl]: https://atcoder.jp/contests/oidashi/tasks/oidashi_a あなたは、道端で怪しげな迷路ジェネレーターを拾ってしまいました。 迷路ジェネレーターを動かすと、縦$ H $マス、横$ W $マスの迷路を自動で生成してくれます。 しかし、それには不具合があり、ゴールにたどり着くことのできない迷路を生成するようでした。 そこで、あなたは迷路を修正し、ゴールにたどり着くことのできるようにすることにしました。 迷路には、壁`#`と道`.`があり、スタートのマス`S`とゴールのマス`G`が$ 1 $マスずつあります。 プレイヤーは、スタートのマスから移動を始め、隣接する縦横4マスの壁でないマスへ移動しながら、ゴールのマスを目指します。 あなたは、ここから壁のマスを **1マスのみ** 道のマスに替えることで、ゴールにたどり着くことのできる迷路を作ることにしました。 ただし、ただ適当な壁を道に変えるでは面白くないと考えたあなたは、スタートからゴールまでの最短経路長が **最長** になるように壁を道に変えることにしました。 上記の操作を行った場合の、スタートからゴールまでの最短経路長を答えてください。

> $ H $ $ W $ $ line_1 $ $ line_2 $ ... $ line_H $ - 1行目には、迷路の高さ$ H $と、迷路の幅$ W $ $ (2\ \leq\ H,\ W\ \leq\ 298) $が与えられます。 - 2行目以降の$ H $行には、$ W $文字の文字列$ line_i $が与えられます。各$ line_i\ (1\ \leq\ i\ \leq\ H) $は、`#`,`.`,`S`,`G`で構成されており、`#`が壁、`.`が道、`S`がスタート地点、`G`がゴール地点を表します。 なお、`S`,`G`は迷路の中に必ず$ 1 $つづつ存在します。 与えられる迷路は、`S`から`G`へたどり着くことができず、必ず1マスの壁を道に替えるとゴールへたどりつけることが保証されています。

修正した迷路のゴールまでの最短経路長を$ 1 $行で出力してください。 出力の末尾には改行を入れること。

### Sample Explanation 2 ループするような道もありえます ### Sample Explanation 3 厚い壁もありえます ### Sample Explanation 4 最初から`S`、`G`どちらとも繋がっていない道もありえます