AT_arc040_d [ARC040D] カクカク塗り

[problemUrl]: https://atcoder.jp/contests/arc040/tasks/arc040_d イカの高橋君は床を塗るのが大好きです。床は $ N\ \times\ N $ のマス目状に区切られており、いくつか（$ 0 $ 個もありうる）のマスには障害物があります。高橋君はこの床を以下のルールで塗ろうと考えています。 - 「今いるマスの床を塗って、上下左右いずれかの隣のマスに移動する」という行動を繰り返す。 - 移動するたびに向きを $ 90 $ 度回転する。すなわち、上または下に移動した直後には右または左に移動し、右または左に移動した直後には上または下に移動する。 - すでに塗ったマスには移動しない。 - マス目の外や障害物のあるマスには移動しない。 高橋君は、すでにどのマスからスタートするかを決めています。このとき、高橋君はうまく移動しながら床を塗ることで、障害物のない全てのマスを塗ることが可能でしょうか。ただし、スタート直後の移動方向や最後に塗るマスには特に指定はありません。また、最後のマスを塗った直後には移動する必要はありません。

入力はイカの形式で標準入力から与えられる。 > $ N $ $ S_1 $ $ S_2 $ : $ S_N $ - $ 1 $ 行目には、マス目の $ 1 $ 辺の個数を表す整数 $ N\ (2\ ≦\ N\ ≦\ 400) $ が与えられる。 - $ 2 $ 行目からの $ N $ 行には、マス目の情報が与えられる。このうち $ i\ (1\ ≦\ i\ ≦\ N) $ 行目には、長さ $ N $ の文字列 $ S_i $ が与えられる。このうち $ j\ (1\ ≦\ j\ ≦\ N) $ 文字目は、$ i $ 行目 $ j $ 列目のマスの情報を以下のように表す。 - `.` の場合：このマスが床であることを表す。 - `#` の場合：このマスに障害物があることを表す。 - `s` の場合：このマスは床であり、高橋君がスタートしようと決めているマスであることを表す。 ただし、これらの文字列の中には `s` がちょうど $ 1 $ つ存在すること、`.` が少なくとも $ 1 $ つ以上存在することが保証される。

全てのマスを塗ることが可能ならば `POSSIBLE`、そうでない場合は `IMPOSSIBLE` を $ 1 $ 行に出力せよ。出力の末尾に改行を入れること。

### 部分点 この問題には部分点が設定されている。 - $ N\ ≦\ 50 $ を満たすデータセット $ 1 $ に正解した場合は、$ 40 $ 点が与えられる。 - 全てのテストケースに正解した場合は、上記とは別に $ 60 $ 点が与えられる。 ### Sample Explanation 1 図のように移動しながら塗れば良いです。 !\[figure\](http://arc040.contest.atcoder.jp/img/arc/040/51381a54b87364aa2348975a838ef330/kaqkaq.png)