矩阵排序

题目描述

给定一个元素均为非负整数的矩阵 $A$。 对于满足 $1 \le i \le H$ 且 $1 \le j \le W$ 的整数对 $(i, j)$,用 $A_{i, j}$ 表示 $A$ 中第 $i$ 行第 $j$ 列的元素。

对 $A$ 进行以下操作。

首先,将 $A$ 中每个为 $0$ 的元素替换为任意正整数(如果有多个元素为 $0$,它们可以替换为不同的正整数)。

然后,按自己的意愿重复执行以下两种操作之一任意次(可以为 $0$ 次)。

• 选择满足 $1 \le i \lt j \le H$ 的整数对 $(i, j)$,交换 $A$ 的第 $i$ 行和第 $j$ 行。
• 选择满足 $1 \le i \lt j \le W$ 的整数对 $(i, j)$,交换 $A$ 的第 $i$ 列和第 $j$ 列。

判断能否使 $A$ 满足以下条件。

$A_{1, 1} \le A_{1, 2} \le \cdots \le A_{1, W} \le A_{2, 1} \le A_{2, 2} \le \cdots \le A_{2, W} \le A_{3, 1} \le \cdots \le A_{H, 1} \le A_{H, 2} \le \cdots \le A_{H, W}$。

换句话说,对于任意两对整数 $(i, j)$ 和 $(i', j')$,其中 $1 \le i, i' \le H$ 且 $1 \le j, j' \le W$,以下两个条件均满足。

• 若 $i \lt i'$,则 $A_{i, j} \le A_{i', j'}$。
• 若 $i = i'$ 且 $j \lt j'$,则 $A_{i, j} \le 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。

样例

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。

数据范围

• $2 \le H, W$
• $H \times W \le 10^6$
• $0 \le A_{i, j} \le H \times W$
• 输入中的所有值均为整数。