AT_abc420_d [ABC420D] Toggle Maze

$ H $ 行 $ W $ 列のグリッドがあります。上から $ i $ 行目、左から $ j $ 列目のマス目を $ (i,j) $ と表します。各マスの状態は文字 $ A_{i,j} $ で表され、意味は以下の通りです。 - `.` ：空きマス。 - `#` ：障害物マス。 - `S` ：スタートマス。 - `G` ：ゴールマス。 - `o` ：開いたドアのマス。 - `x` ：閉じたドアのマス。 - `?` ：スイッチマス。 高橋君は、 $ 1 $ 回の操作で今いるマスから上下左右に隣り合う、障害物マスでも閉じたドアでもないマスへ移動することができます。 また、スイッチマスに移動する度に全ての開いたドアのマスは閉じたドアのマスに、閉じたドアのマスは開いたドアのマスに変わります。 高橋君がはじめスタートマスにいる状態からゴールマスにいる状態にするよう操作できるか判定し、可能な場合は必要な操作回数の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ A_{1,1}A_{1,2}\cdots A_{1,W} $ $ A_{2,1}A_{2,2}\cdots A_{2,W} $ $ \vdots $ $ A_{H,1}A_{H,2}\cdots A_{H,W} $

高橋君がはじめスタートマスにいる状態からゴールマスにいる状態するよう操作できる場合は必要な操作回数の最小値を、できない場合は $ -1 $ を出力せよ。

### Sample Explanation 1 $ (1,1) $ から順に $ (1,2),(2,2),(1,2),(1,3),(1,4) $ と移動するよう操作することで $ 5 $ 回の操作でゴールマスにいる状態にすることができます。 ### Sample Explanation 2 どのように操作してもゴールマスにいる状態にすることはできません。したがって、 $ -1 $ を出力してください。 ### Constraints - $ 1\le H,W \le 500 $ - $ H,W $ は整数 - $ A_{i,j} $ は `.`, `#`, `S`, `G`, `o`, `x`, `?` のいずれか - `S` と `G` は $ A_{i,j} $ にそれぞれちょうど $ 1 $ つずつ存在する