問題文

H 行 W 列のグリッドが与えられます。上から i 行目、左から j 列目のマスをマス (i,j) と表します。各マスには E, F, G のいずれかの文字が書かれており、マス (i,j) に書かれた文字は与えられる文字列 S_i の j 文字目と同じです。

はじめ、マス (1,1) にコマが置かれています。あなたの目標はこのコマを四方向に隣接するマスに動かす操作を繰り返してマス (H,W) にコマが置かれた状態にすることです。

ただし、各操作で今いるマスと同じ文字が書かれたマスへ移動することはできません。

マス (H,W) にコマが置かれた状態にすることが可能か判定し、可能な場合は操作回数の最小値を求めてください。

制約

• 2\le H\le 1000
• 2\le W\le 1000
• H,W は整数
• S_i は E, F, G からなる長さ W の文字列

入力例 1

3 4
EEGE
GFFF
GFEE

出力例 1

7

マス (1,1) から順にマス (2,1),(2,2),(1,2),(1,3),(1,4),(2,4),(3,4) と順に動かしていけば良いです。

この場合の操作回数は 7 回で、 7 回未満でマス (3,4) にコマが置かれた状態にすることはできません。したがって、 7 を出力してください。

入力例 2

2 2
EE
FF

出力例 2

-1

マス (2,2) にコマが置かれた状態にすることはできません。したがって、 -1 を出力してください。

入力例 3

5 6
FEGFGF
FEEFEE
FFGGFE
GEGGEE
GGEGFE

出力例 3

9