题目描述

縦横 $H\ \times\ W$ マスのグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ と表します。
各マスの状態は $C_{i,j}$ で表されます。各マスの状態は次の $4$ つのいずれかです。

• S : スタート地点。グリッド上にちょうど $1$ つだけ存在する。
• G : ゴール地点。グリッド上にちょうど $1$ つだけ存在する。
• . : 壁を建ててよいマス。
• O : 壁を建ててはいけないマス。

青木君はスタート地点を出発してグリッド上を移動してゴール地点へ行こうとしています。青木君は $(i,j)$ にいるときにマス $(i+1,j),(i,j+1),(i-1,j),(i,j-1)$ のいずれかに移動することができます。ただし、グリッドの外に出るような移動や、壁があるマスへの移動を行うことはできません。

高橋君は、青木君が移動を開始する前に壁を建ててよいマスを $1$ マス以上選んで壁を建てることで、青木君がどのように移動してもゴール地点へ行くことができないようにすることにしました。ただし、スタート地点およびゴール地点は選ぶことができません。

高橋君は青木君がゴールできないように壁を建てることができますか？さらに、壁を建てられる場合は

• 青木君がゴールできないように壁を建てるときの最小枚数 $n$ 、および
• 最小枚数を達成する壁の立て方が何通りあるかを $998244353$ で割ったあまり $r$

の $2$ つも合わせて計算してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$H$ $W$ $C_{1,1}$$C_{1,2}$$\dots$$C_{1,W}$ $C_{2,1}$$C_{2,2}$$\dots$$C_{2,W}$ $\vdots$ $C_{H,1}$$C_{H,2}$$\dots$$C_{H,W}$

输出格式

青木君がゴールできないように壁を建てられる場合は、文字列 Yes 、および問題文中で定義された整数 $n$, $r$ を以下の形式で出力せよ。

Yes $n$ $r$

そうでない場合は No を出力せよ。

题目大意

良心翻译

题目描述了一个大小为 H × W 的网格，每个格子有四种状态：S（起始点）、G（目标点）、.（可建墙的空白格子）和O（不可建墙的格子）。青木君在起始点出发，可以向上下左右四个方向移动到相邻的空白格子，但不能越过网格边界或者移动到墙上。

现在高桥君想要在青木君开始移动之前，选择至少一个格子来建墙，以阻止青木君无论如何都无法到达目标点。特别地，起始点和目标点不能被选中。

你需要判断是否存在一种方式可以建墙使得青木君无法到达目标点。如果存在这样的方式，还需要计算建墙的最小数量 n，并计算满足最小数量的建墙方式总数 r（取模 998244353）。

输出格式要求：

如果可以建墙使得青木君无法到达目标点，则输出字符串"Yes"，并且输出整数 n 和 r。 如果无法建墙阻止青木君到达目标点，则输出字符串"No"。

4 3
S..
O..
..O
..G

Yes
3 6

3 2
.G
.O
.S

No

2 2
S.
.G

Yes
2 1

10 10
OOO...OOO.
.....OOO.O
OOO.OO.OOO
OOO..O..S.
....O.O.O.
.OO.O.OOOO
..OOOG.O.O
.O.O..OOOO
.O.O.OO...
...O..O..O

Yes
10 12

提示

制約

• $2\ \leq\ H\ \leq\ 100$
• $2\ \leq\ W\ \leq\ 100$
• $C_{i,j}$ は S, G, ., O のいずれかである。
• S, G は $C_{i,j}$ の中でちょうど $1$ 回だけ登場する。

Sample Explanation 1

壁を建てるマスを # で表すと、最小枚数を達成する壁の建て方は次の $6$ 通りとなります。 S#. S.# S.. S.. S.. S.. O#. O#. O## O.# O.# O.# #.O #.O #.O ##O .#O .#O ..G ..G ..G ..G #.G .#G

Sample Explanation 2

高橋君がどのように壁を建てても青木君はゴール地点へ行くことができます。