グリッド上の最短経路

r 行 c 列のグリッドで表される迷路が与えられているとき、スタートのセルからゴールのセルまでの最短経路の長さを求める問題です。

迷路は以下のように表されています:

• 床はドット (.)

• 壁はハッシュ (#)

• スタート地点は大文字の S

• ゴール地点は大文字の E

壁ではない隣接セル（上下左右）であれば移動可能です。

スタートのセルからゴールのセルまでの最短経路の長さを見つけるのが目的です。

入力

最初の行には、2 つの整数 r と c (1 ≤ r, c ≤ 1000) が与えられます。

続く r 行には、c 列分の文字が並んでおり、各セルは床 (.)、壁 (#)、スタート (S)、またはゴール (E) のいずれかです。グリッド全体で S と E はそれぞれ 1 つだけ存在することが保証されています。

出力

プログラムは、S から E までの最短経路の長さを出力してください。もし S から E へ到達できる経路が存在しない場合は、Impossible を出力してください。

例

Input

5 8
########
##.S....
....#.#.
#......#
...#...E

Output

7