問題文

良く見てみるとカードの有効期限が切れていたので、高橋君は諦めて魚屋に直接うなぎを買いに行くことにしました。
　彼の住む街は長方形の形をしており、格子状の区画に区切られています。区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。また、塀の区画は通ることができません。高橋君の家から魚屋までの道のりは非常に複雑なため、単純に歩くだけでは辿り着くことは困難です。
　しかし、高橋君は腕力には自信があるので道に上下左右で面している塀を $2$ 回までなら壊して道にすることができます。

高橋君が魚屋に辿り着くことができるかどうか答えてください。

---

入力

入力は以下の形式で標準入力から与えられる。$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$ 行ある。

• $1$ 行目は、街の南北の長さとして整数 $H(1≦H≦500)$ と東西の長さとして整数 $W(1≦W≦500)$ が空白で区切られて与えられる。

• $2$ 行目からの $H$ 行には、格子状の街の各区画における状態 $c_{(i,j)}(0≦i≦H-1,$ $0≦j≦W-1)$ が与えられる。

• $i$ 行目 $j$ 文字目の文字 $c_{(i,j)}$ はそれぞれ s, g, ., # のいずれかで与えられ、座標 $(j,i)$ が下記のような状態であることを表す。

• s : その区画が家であることを表す。

• g : その区画が魚屋であることを表す。

• . : その区画が道であることを表す。

• # : その区画が塀であることを表す。

• 高橋君は家・魚屋・道は通ることができるが、塀は通ることができない。

• 与えられた街の外を通ることはできない。

• s と g はそれぞれ $1$ つずつ与えられる。

出力

塀を $2$ 回まで越えることで、家から魚屋まで辿り着くことができる場合は YES、辿りつけない場合は NO を標準出力に $1$ 行で出力せよ。
なお、最後には改行を出力せよ。

---

入力例 1

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

出力例 1

YES

$(1,2),$ $(2,2),$ $(3,2)$ のいずれかの塀を壊すことで、魚屋に到達することができます。

---

入力例 2

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

出力例 2

YES

• 塀が無いので到達することができます。

---

入力例 3

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

出力例 3

YES

• $(1,6),$ $(2,6)$ の $2$ つの塀を壊すことで到達することができます。

---

入力例 4

6 6
.....s
###...
###...
######
...###
g.####

出力例 4

YES

• 一例として $(3,3)$, $(2,3),$ の $2$ つの塀を壊すと、到達することができます。

---

入力例 5

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

出力例 5

NO

• 塀を $2$ つ壊しても魚屋に到達することができません。

---

Source Name

ARC 005

---