配点 : $500$ 点

問題文

非負整数を要素とする $H$ 行 $W$ 列の行列 $A$ が与えられます。 $1 \leq i \leq H$ かつ $1 \leq j \leq W$ を満たす整数の組 $(i, j)$ について、 $A$ の $i$ 行目 $j$ 列目の要素を $A_{i, j}$ で表します。

$A$ に対して以下の手順を行います。

• まず、$A$ の要素のうち $0$ であるものそれぞれを、任意の正の整数で置き換える（ $0$ である要素が複数ある場合、それぞれを異なる正の整数で置き換えることもできます）。
• その後、「下記の $2$ つの操作のどちらかを行うこと」を好きな回数（ $0$ 回でも良い）だけ行う。
  • $1 \leq i \lt j \leq H$ を満たす整数の組 $(i, j)$ を選び、$A$ の $i$ 行目と $j$ 行目を入れ替える。
  • $1 \leq i \lt j \leq W$ を満たす整数の組 $(i, j)$ を選び、$A$ の $i$ 列目と $j$ 列目を入れ替える。
• $1 \leq i \lt j \leq H$ を満たす整数の組 $(i, j)$ を選び、$A$ の $i$ 行目と $j$ 行目を入れ替える。
• $1 \leq i \lt j \leq W$ を満たす整数の組 $(i, j)$ を選び、$A$ の $i$ 列目と $j$ 列目を入れ替える。

$A$ が次の条件を満たすようにすることができるかどうかを判定してください。

• $A_{1, 1} \leq A_{1, 2} \leq \cdots \leq A_{1, W} \leq A_{2, 1} \leq A_{2, 2} \leq \cdots \leq A_{2, W} \leq A_{3, 1} \leq \cdots \leq A_{H, 1} \leq A_{H, 2} \leq \cdots \leq A_{H, W}$
• 言い換えると、$1 \leq i, i' \leq H$ および $1 \leq j, j' \leq W$ を満たす任意の $2$ つの整数の組 $(i, j)$ と $(i', j')$ について、下記の $2$ つの条件がともに成り立つ。
  • $i \lt i'$ ならば $A_{i, j} \leq A_{i', j'}$
  • 「 $i = i'$ かつ $j \lt j'$ 」ならば $A_{i, j} \leq A_{i', j'}$
• $i \lt i'$ ならば $A_{i, j} \leq A_{i', j'}$
• 「 $i = i'$ かつ $j \lt j'$ 」ならば $A_{i, j} \leq A_{i', j'}$

制約

• $2 \leq H, W$
• $H \times W \leq 10^6$
• $0 \leq A_{i, j} \leq H \times W$
• 入力はすべて整数

入力

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

$H$ $W$

$A_{1, 1}$ $A_{1, 2}$ $\ldots$ $A_{1, W}$

$A_{2, 1}$ $A_{2, 2}$ $\ldots$ $A_{2, W}$

$\vdots$

$A_{H, 1}$ $A_{H, 2}$ $\ldots$ $A_{H, W}$

出力

$A$ が問題文中の条件を満たすようにできる場合は Yes を、できない場合は No を出力せよ。

3 3
9 6 0
0 4 0
3 0 3

Yes

以下の手順で操作を行うことで、$A$ が問題文中の条件を満たすようにすることができるため、Yes を出力します。

• まず、$A$ の $0$ である要素を下記の通りに置き換える。

9 6 8
5 4 4
3 1 3

• $2$ 列目と $3$ 列目を入れ替える。その結果、$A$ は下記の通りとなる。

9 8 6
5 4 4
3 3 1

• $1$ 行目と $3$ 行目を入れ替える。その結果、$A$ は下記の通りとなる。

3 3 1
5 4 4
9 8 6

• $1$ 列目と $3$ 列目を入れ替える。その結果、$A$ は下記の通りとなり、問題文中の条件を満たすようになる。

1 3 3
4 4 5
6 8 9

2 2
2 1
1 2

No

どのように操作を行っても $A$ が問題文中の条件を満たすようにすることはできないため、No を出力します。