AT_abc277_f [ABC277F] Sorting a Matrix

给定一个 $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$，可以分别替换为不同的正整数）。 - 然后，可以任意次（也可以不进行）执行以下两种操作中的任意一种： - 选择满足 $1 \leq i < j \leq H$ 的整数对 $(i, j)$，交换 $A$ 的第 $i$ 行和第 $j$ 行。 - 选择满足 $1 \leq i < 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$ 的两个整数对 $(i, j)$ 和 $(i', j')$，都满足以下两个条件： - 如果 $i < i'$，则 $A_{i, j} \leq A_{i', j'}$。 - 如果 $i = i'$ 且 $j < 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`。

## 限制 - $2 \leq H, W$ - $H \times W \leq 10^6$ - $0 \leq A_{i, j} \leq H \times W$ - 输入均为整数 ## 样例解释 1 可以通过如下步骤操作，使 $A$ 满足题目中的条件，因此输出 `Yes`。 - 首先，将 $A$ 中的 $0$ 元素替换如下： ``` 9 6 8 5 4 4 3 1 3 ``` - 交换第 2 列和第 3 列，结果如下： ``` 9 8 6 5 4 4 3 3 1 ``` - 交换第 1 行和第 3 行，结果如下： ``` 3 3 1 5 4 4 9 8 6 ``` - 交换第 1 列和第 3 列，结果如下，满足题目条件： ``` 1 3 3 4 4 5 6 8 9 ``` ## 样例解释 2 无论如何操作，都无法使 $A$ 满足题目中的条件，因此输出 `No`。 由 ChatGPT 4.1 翻译