AT_arc040_d [ARC040D] カクカク塗り

高桥君非常热爱涂地板。地板被分成了一个 $N \times N$ 的网格，其中有些格子上可能存在障碍物（包括可能一个障碍物都没有）。他计划按照以下规则来涂地板： - 重复以下操作：「将当前所在的格子涂色，然后移动到上下左右相邻的格子之一」。 - 每次移动后需要顺时针旋转 $90$ 度。具体来说，刚刚向上或向下移动完后，接下来的移动方向必须是水平的；刚刚向左或向右移动完后，接下来的移动方向必须是垂直的。 - 不能移动到已经涂过色的格子。 - 不能移出网格边界或移动到障碍物所在的格子。 高桥君已经选择好了起点格子。请判断他是否可以通过合理的路径，将所有没有障碍物的格子全部涂色。注意，初始的移动方向和最终停下的格子没有特别要求。在涂完最后一个格子之后，也不需要再进行移动。

标准输入给出如下数据： - 第一行包含一个整数 $N\ (2 \leq N \leq 400)$，表示网格的大小。 - 接下来 $N$ 行中每行包含一个长度为 $N$ 的字符串 $S_i$，描述网格的状态。 - `.` 表示该格子是可涂色的地板。 - `#` 表示该格子有障碍物，不可涂色。 - `s` 表示起始格子，高桥君将从此处出发。 保证输入中恰有一个 `s`，且至少有一个 `.`。

如果高桥君能将所有没有障碍物的格子全部涂色，输出 `POSSIBLE`；否则，输出 `IMPOSSIBLE`。输出结果需要另起一行。

### 部分分数 题目设有部分分数： - 对于满足 $N \leq 50$ 的数据集，正确解答可获得 $40$ 分。 - 对于所有测试用例，若能正确解答，可额外获得 $60$ 分。 ### 样例说明 1 通过给定的移动规则，可以如图所示地依次涂色。 !\[figure\](http://arc040.contest.atcoder.jp/img/arc/040/51381a54b87364aa2348975a838ef330/kaqkaq.png) **本翻译由 AI 自动生成**