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.