题目描述

非負整数を要素とする $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$ 列目を入れ替える。

$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'}$

输入格式

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

$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 を出力せよ。

题目大意

给定一个 $H \times W$ 的矩阵，其中第 $i$ 行第 $j$ 列的数字为 $A_{i,j}$，如果 $A_{i,j}=0$，那么你需要将其替换为任意正整数。

你现在有两种操作：

• 选择两行 $i,j$，交换这两行的数字。
• 选择两列 $i,j$，交换这两列的数字。

你希望交换之后满足 $A_{1,1} \leq A_{1,2} \leq A_{1,3} \leq \dots \leq A_{1,W} \leq A_{2,1} \leq \dots \leq A_{2,W} \leq \dots \leq A_{H,W}$。

如果存在至少一种替换数字的方案和操作方案，输出 Yes，否则输出 No。

3 3
9 6 0
0 4 0
3 0 3

Yes

2 2
2 1
1 2

No

提示

制約

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

Sample Explanation 1

以下の手順で操作を行うことで、$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

Sample Explanation 2

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