あなたは一方通行迷路ゲームというコンピュータゲームで遊んでいる。このゲームでは、H行W列のマスで区切られた長方形が画面上に表示される。各マスは壁、道、スタート、ゴールのいずれかで、スタートとゴールはそれぞれ一つだけである。道のマスとスタートのマスでは、上下左右に隣接する道のマスかゴールのマスだけに進むことができる。ただし、道のマスのうちいくつかは一方通行のマスであり、上下左右のうち一つの方向にしか出られない。
1回のゲームでは、スタートから出発して道を通ってゴールを目指す。ゴールにたどりつければゲームクリア、たどりつけないことがわかった時点でゲームオーバーである。スタートからゴールまでの移動回数が少ないほど、ランキングが上がる。ゲーム中で一度だけ、一方通行のマスを一つ選んでその方向を好きな方向に変えることができる。ランキング上位を目指すために、あなたは画面をよく見て、どの一方通行のマスを選んで方向を変えればいいか、よく検討しなければならない。
画面上に各マスの情報が与えられたとき、スタートからゴールにたどりつけるかどうか判定し、たどりつけるときは最小の移動回数を報告するプログラムを作成せよ。
入力は以下の形式で与えられる。
$H$ $W$
$s_{1,1}$ $s_{1,2}$ ... $s_{1,W}$
$s_{2,1}$ $s_{2,2}$ ... $s_{2,W}$
:
$s_{H,1}$ $s_{H,2}$ ... $s_{H,W}$
１行目に画面上の長方形の行の数$H$ ($2 \leq H \leq 300$)、列の数$W$ ($2 \leq W \leq 300$)が与えられる。続く$H$行に$i$行$j$列目のマスを表す文字$s_{i,j}$が与えられる。各$s_{i,j}$は以下のどれか一つである。
| . | 一方通行ではない道 |
| # | 壁 |
| U,D,L,R | 一方通行の道。それぞれ、上、下、左、右の方向へだけ出られるマスを表す。 |
| S,G | Sがスタート、Gがゴール。 |
スタートからゴールにたどりつく最小の移動回数を1行に出力する。ただし、たどりつけないときは「-1」を出力する。
4 5 ##S## #..## #.DG. #..##
3
4 3 #S. #U. GD. ###
5
3 4 #..# .LDG .S#.
-1