题目描述

我们有一个从上到下有 $H$ 行，从左到右有 $W$ 列的网格。记 $(i, j)$ 为从上往下数第 $i$ 行（$1 \\leq i \\leq H$）和从左往右数第 $j$ 列（$1 \\leq j \\leq W$）。

每个方格可以是以下之一：初始点、道路或障碍物。
方格 $(i, j)$ 由字符 $C_{i, j}$ 表示。如果 $C_{i, j} =$ S，则该方格是初始点；如果 $C_{i, j} =$ .，则是道路；如果 $C_{i, j} =$ #，则是障碍物。初始点只有一个。

判断是否存在一条长度至少为 $4$ 的路径，该路径从初始点开始，重复向相邻的方格垂直或水平移动，并在不通过障碍物或多次访问同一方格的情况下返回到初始点。
更具体地说，判断是否存在一个整数 $n$ 和一系列方格 $(x_0, y_0), (x_1, y_1), \\dots, (x_n, y_n)$，满足以下条件。

• $n \\geq 4$。
• $C_{x_0, y_0} = C_{x_n, y_n} =$ S。
• 如果 $1 \\leq i \\leq n - 1$，则 $C_{x_i, y_i} =$ .。
• 如果 $1 \\leq i \\lt j \\leq n - 1$，则 $(x_i, y_i) \\neq (x_j, y_j)$。
• 如果 $0 \\leq i \\leq n - 1$，则方格 $(x_i, y_i)$ 和方格 $(x_{i+1}, y_{i+1})$ 在垂直或水平方向上相邻。

约束条件

• $4 \\leq H \\times W \\leq 10^6$
• $H$ 和 $W$ 是大于等于 $2$ 的整数。
• $C_{i, j}$ 是 S、. 或 #。
• 有且仅有一个 $(i, j)$ 满足 $C_{i, j} =$ S。

输入

从标准输入读取输入数据，输入格式如下：

$H$ $W$ $C_{1, 1} \\ldots C_{1, W}$ $\\vdots$ $C_{H, 1} \\ldots C_{H, W}$

输出

如果存在满足题目描述条件的路径，则输出 Yes；否则输出 No。

样例输入 1

4 4
....
.#..
.S..
.##.

样例输出 1

Yes

路径 $(3, 2) \\rightarrow (2, 2) \\rightarrow (1, 2) \\rightarrow (1, 3) \\rightarrow (1, 4) \\rightarrow (2, 4) \\rightarrow (3, 4) \\rightarrow (3, 3) \\rightarrow (3, 2)$ 满足题目条件。

样例输入 2

2 2
S.
.#

样例输出 2

No

样例输入 3

5 7
.#...#.
..#.#..
...S...
..#.#..
.#...#.

样例输出 3

No