AT_utpc2021_l Maze Game

[problemUrl]: https://atcoder.jp/contests/utpc2021/tasks/utpc2021_l 縦 $ H $ 行、横 $ W $ 列のグリッド状の迷路があります。 各マスには `S` , `G` , `#` , `.` のいずれかの文字が書かれています。$ i $ 行目 $ j $ 列目のマスに書かれている文字は$ c_{i,j} $ です。`#` と書かれたマスは壁になっており、そうでないマスは壁ではありません。 また、`S` と `G` は $ 1 $ つずつで、上下左右に隣接していないことが保証されます。 迷路が次の条件を満たす時、**到達可能な状態** と呼ぶことにします。 - `S` と書かれたマスから、`G` と書かれたマスに、上下左右に隣接する壁でないマス (つまり `#` と書かれてないマス) のみを通って到達できる。 ただし、迷路の外に出るような移動はできない。 最初、迷路は **到達可能な状態** であることが保証されます。 Alice と Bob がこの迷路を使ってゲームをします。 Alice が先手で、交互に以下の操作を行います。 - `.` と書かれたマスを $ 1 $ つ選び、 `#` と書かれたマスに変更する。 先に自分の操作終了時に、迷路が **到達可能な状態** でなくなったプレイヤーの勝利となります。 本問題の制約下で与えられる迷路では、必ず勝者が決定することが証明できます。 二人が最適に行動した場合、どちらが勝つか求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \vdots $ $ \mathrm{case}_T $ 各ケースは以下の形式で与えられる。 > $ H $ $ W $ $ c_{1,1}c_{1,2}\ldots\ c_{1,W} $ $ c_{2,1}c_{2,2}\ldots\ c_{2,W} $ $ \vdots $ $ c_{H,1}c_{H,2}\ldots\ c_{H,W} $

各テストケースについて、Aliceが勝つ場合は `Alice`、Bobが勝つ場合は `Bob` と出力せよ。

### 制約 - $ 1\ \le\ T\ \le\ 50 $ - $ 2\ \le\ H,W\ \le\ 100 $ - 迷路に含まれる文字は、`S`, `G`, `.`, `#` のいずれか - `S` と `G` は 1 つずつ含まれ、上下左右に隣接していない - 与えられる迷路は **到達可能な状態** である ### Sample Explanation 1 1つめのケースでは、Aliceが選べるマスは右上か左下の2通りですが、どちらを選んでも次にBobがもう一方の `.` であるマスを選択してBobが勝ちます。 2つめのケースでは、Aliceが2行目の `.` を `#` に変えてAliceの勝利となります。