问题文

这个问题是一个讲座用的问题。解答在页面底部。

高桥君所住的城市是一个长方形，被格子状的区块划分。城市的边界平行于东西和南北方向。每个区块可以是道路或者围墙，高桥君可以在道路上向东、西、南、北方向移动，但不能斜向移动。另外，他无法穿过围墙区块。

请判断高桥君是否能够到达鱼店，而不需要破坏或穿越任何围墙。

---

输入

输入以以下格式从标准输入中给出。

$H$ $W$ $c_{0,0}$ $c_{0,1}$ $c_{0,W-1}$ $c_{1,0}$ $c_{1,1}$ $c_{1,W-1}$ : $c_{H-1,0}$ $c_{H-1,1}$ $c_{H-1,W-1}$

• 第一行输入两个整数 $H(1≦H≦500)$ 和 $W(1≦W≦500)$，分别表示城市的南北长度和东西长度，两者之间用空格隔开。
• 接下来的 $H$ 行表示格子状城市中每个区块的状态 $c_{i,j}(0≦i≦H-1, 0≦j≦W-1)$。
  • 第 $i$ 行第 $j$ 列的字符 $c_{i,j}$ 可以是 s, g, ., # 中的一个，分别表示以下状态：
    • s : 该区块是高桥君的家。
    • g : 该区块是鱼店。
    • . : 该区块是道路。
    • # : 该区块是围墙。
  • 高桥君可以通过家、鱼店和道路区块，但不能通过围墙区块。
  • 不能离开给定的城市范围。
  • s 和 g 分别只会出现一次。

输出

如果高桥君能够在不破坏任何围墙的情况下从家到达鱼店，则输出 Yes，否则输出 No，结果只占一行。

解释

使用深度优先搜索进行填充 来自 AtCoder Inc.

---

输入示例1

4 5
s####
....#
#####
#...g

输出示例1

No

高桥君无法到达鱼店。

---

输入示例2

4 4
...s
....
....
.g..

输出示例2

Yes

---

输入示例3

10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
###.#.#.#.
#.....#...

输出示例3

No

---

输入示例4

10 10
s.........
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
g.#.#.#.#.
#.#.#.#.#.
#.#.#.#.#.
#.....#...

输出示例4

Yes

---

输入示例5

1 10
s..####..g

输出示例5

No

---