{"problem":{"name":"Sorting a Matrix","description":{"content":"You are given a matrix $A$ whose elements are non-negative integers. For a pair of integers $(i, j)$ such that $1 \\leq i \\leq H$ and $1 \\leq j \\leq W$, let $A_{i, j}$ denote the element at the $i$\\-th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc277_f"},"statements":[{"statement_type":"Markdown","content":"You are given a matrix $A$ whose elements are non-negative integers. For a pair of integers $(i, j)$ such that $1 \\leq i \\leq H$ and $1 \\leq j \\leq W$, let $A_{i, j}$ denote the element at the $i$\\-th row and $j$\\-th column of $A$.\nLet us perform the following procedure on $A$.\n\n*   First, replace each element of $A$ that is $0$ with an arbitrary **positive integer** (if multiple elements are $0$, they may be replaced with different positive integers).\n*   Then, repeat performing one of the two operations below, which may be chosen each time, as many times as desired (possibly zero).\n    *   Choose a pair of integers $(i, j)$ such that $1 \\leq i \\lt j \\leq H$ and swap the $i$\\-th and $j$\\-th rows of $A$.\n    *   Choose a pair of integers $(i, j)$ such that $1 \\leq i \\lt j \\leq W$ and swap the $i$\\-th and $j$\\-th columns of $A$.\n\nDetermine whether $A$ can be made to satisfy the following condition.\n\n*   $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}$.\n*   In other words, for every two pairs of integers $(i, j)$ and $(i', j')$ such that $1 \\leq i, i' \\leq H$ and $1 \\leq j, j' \\leq W$, both of the following conditions are satisfied.\n    *   If $i \\lt i'$, then $A_{i, j} \\leq A_{i', j'}$.\n    *   If $i = i'$ and $j \\lt j'$, then $A_{i, j} \\leq A_{i', j'}$.\n\n## Constraints\n\n*   $2 \\leq H, W$\n*   $H \\times W \\leq 10^6$\n*   $0 \\leq A_{i, j} \\leq H \\times W$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$H$ $W$\n$A_{1, 1}$ $A_{1, 2}$ $\\ldots$ $A_{1, W}$\n$A_{2, 1}$ $A_{2, 2}$ $\\ldots$ $A_{2, W}$\n$\\vdots$\n$A_{H, 1}$ $A_{H, 2}$ $\\ldots$ $A_{H, W}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc277_f","tags":[],"sample_group":[["3 3\n9 6 0\n0 4 0\n3 0 3","Yes\n\nOne can perform the operations as follows to make $A$ satisfy the condition in the problem statement, so you should print `Yes`.\n\n*   First, replace the elements of $A$ that are $0$, as shown below:\n\n9 6 8\n5 4 4\n3 1 3\n\n*   Swap the second and third columns. Then, $A$ becomes:\n\n9 8 6\n5 4 4\n3 3 1\n\n*   Swap the first and third rows. Then, $A$ becomes:\n\n3 3 1\n5 4 4\n9 8 6\n\n*   Swap the first and third columns. Then, $A$ becomes the following and satisfies the condition in the problem statement.\n\n1 3 3\n4 4 5\n6 8 9"],["2 2\n2 1\n1 2","No\n\nThere is no way to perform the operations to make $A$ satisfy the condition in the problem statement, so you should print `No`."]],"created_at":"2026-03-03 11:01:13"}}