P17900 [ICPC 2026 Nanchang I] Kingdam of Construction

Description

You are managing the valve matrix of the “Kingdam of Construction”. Given an $n\times m$ matrix $a$ (both $n$ and $m$ are even), where all elements of $a$ are distinct positive integers between $1$ and $n\times m$. You can perform the following two types of operations in any order: - Choose row $i$ ($1\le i\le n$) and reverse it left-to-right, i.e. for all $1\le j\le \frac m2$, swap $a_{i,j}$ and $a_{i,m-j+1}$; - Choose column $j$ ($1\le j\le m$) and reverse it top-to-bottom, i.e. for all $1\le i\le \frac n2$, swap $a_{i,j}$ and $a_{n-i+1,j}$. Determine whether it is possible to transform $a$ into the $n\times m$ target matrix $b$ after a finite number of operations, where $b$ is filled in row-major order with $1,2,\ldots,n\times m$, i.e. $b_{i,j}=(i-1)\times m+j$. If it is possible, construct an operation sequence with **no more than $9961$ operations** (it is also allowed to perform no operation, i.e. an empty operation sequence). It can be proved that if an operation sequence exists, then there also exists one with no more than $9961$ operations.

Input Format

The first line contains a positive integer $t$ ($1\le t\le 25$), representing the number of test cases. For each test case: The first line contains two positive integers $n$ and $m$ ($2\le n\le 134$, $2\le m\le 134$), representing the number of rows and columns of matrix $a$. The next $n$ lines each contain $m$ positive integers $a_{i,1},a_{i,2},\ldots,a_{i,m}$, representing the elements of matrix $a$. It is guaranteed that both $n$ and $m$ are even; it is also guaranteed that every integer from $1$ to $n\times m$ appears exactly once in matrix $a$.

Output Format

For each test case: If it is possible to transform matrix $a$ into the target matrix $b$ in finitely many operations, print “`Yes`” on the first line. Then print one non-negative integer $cnt$ on the next line, representing the number of operations. You must ensure that $0\le cnt\le 9961$ (for each test case; that is, there is no restriction on the sum of $cnt$ over all test cases). Then print $cnt$ lines, each containing two integers $op$ and $idx$ ($op\in\{0,1\}$, $1\le idx\le n$ if $op=0$, otherwise $1\le idx\le m$), where $op=0$ means reversing row $idx$, and $op=1$ means reversing column $idx$. If no valid sequence of operations exists, output only one line containing “`No`”. You can output the answer in any case (upper or lower). For example, the strings “`yEs`”, “`yes`”, “`Yes`”, and “`YES`” will be recognized as positive responses.

Explanation/Hint

For the second sample test case, the operation process is as follows: $$ \def \arr #1#2#3#4#5#6#7#8{ \begin{bmatrix} #1 & #2 & #3 & #4\\ #5 & #6 & #7 & #8 \end{bmatrix} } \def \arrRow #1#2#3#4#5#6#7#8{ \begin{bmatrix} \mathbf{#1} & \mathbf{#2} & \mathbf{#3} & \mathbf{#4}\\ #5 & #6 & #7 & #8 \end{bmatrix} } \def \arrCol #1#2#3#4#5#6#7#8{ \begin{bmatrix} #1 & \mathbf{#2} & #3 & #4\\ #5 & \mathbf{#6} & #7 & #8 \end{bmatrix} } \def \toCol {\xrightarrow{\text{column, 2}}} \def \toRow {\xrightarrow{\text{row, 1}}} \begin{array}{cccccc} & \arr 13245678 & \toCol & \arrCol 16245378 & \toRow & \arrRow 42615378 \\ \toCol & \arrCol 43615278 & \toRow & \arrRow 16345278 & \toCol & \arrCol 12345678.\\ \end{array} $$ For the third and fourth sample test cases, the target matrix $b$ is $\begin{bmatrix}1&2\\3&4\\5&6\\7&8\end{bmatrix}$ and $\begin{bmatrix}1&2&3&4\\5&6&7&8\\9&10&11&12\\13&14&15&16\end{bmatrix}$, respectively. It can be proved that both cases have no solution.