F - 排序矩阵

得分：500分

问题描述

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

现在，对矩阵$A$执行以下操作：

• 首先，将$A$中的每一个$0$替换为任意的正整数（如果存在多个$0$，可以将其替换为不同的正整数）。
• 然后，重复以下两个操作中的一个，可以选择每次都进行该操作也可以不进行：
1. 选择一对整数$(i, j)$，满足$1 \leq i < j \leq H$，交换矩阵$A$的第$i$行和第$j$行。
2. 选择一对整数$(i, j)$，满足$1 \leq i < j \leq W$，交换矩阵$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}$。
• 换句话说，对于任意一对整数$(i, j)$和$(i', j')$，满足$1 \leq i, i' \leq H$和$1 \leq j, j' \leq W$，以下条件均满足：
1. 如果$i < i'$，则$A_{i, j} \leq A_{i', j'}$。
2. 如果$i = i'$且$j < 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

• 交换第二列和第三列。此时，矩阵$A$变为：

9 8 6
5 4 4
3 3 1

• 交换第一行和第三行。此时，矩阵$A$变为：

3 3 1
5 4 4
9 8 6

• 交换第一列和第三列。此时，$A$满足问题描述中的条件。

1 3 3
4 4 5
6 8 9

2 2
2 1
1 2

No

无论如何操作，都无法使得矩阵$A$满足问题描述中的条件，因此应输出"No"。