Background

A gentleman is not a mere tool.

“I am best at solving puzzles, right, kid?”

“Hmm...”

Problem Description

Kid walks into a matrix with $n$ rows and $m$ columns. It is not guaranteed that the matrix contains $n$ numbers $1$, $n$ numbers $2$, $\dots$ , $n$ numbers $m$, but both $n$ and $m$ are even numbers.

There are two ways to change the matrix:

• Choose any row and reverse (flip) the numbers in this row.
• Choose any column and reverse (flip) the numbers in this column.

In each operation, you may choose either way.

Now you need to perform several operations to turn the matrix into:

$$n\;行\left\{ \begin{array}{l} 1\quad2\quad3\quad\cdots\quad m\\ \\ 1\quad2\quad3\quad\cdots\quad m\\ \\ \cdots\\ \\ 1\quad2\quad3\quad\cdots\quad m\\ \end{array} \right.$$

Only then will the next save point appear.

You need to help kid solve this problem.

You only need to output an answer; leave the remaining operations to Uvocde!

Input Format

The first line contains two positive integers $n$ and $m$. The next $n$ lines each contain $m$ positive integers, describing the matrix.

Output Format

The first line contains one string. If it is impossible to find a feasible sequence of operations, output NO; otherwise output YES.

If you output YES, output a non-negative integer $ans$ on the next line, indicating that one solution needs $ans$ operations in total. Then output $ans$ lines. Each line contains one character and a number $k$ (separated by a space). The character indicates whether this operation flips a row or a column: 0 means flipping a row, and 1 means flipping a column. $k$ indicates which row or which column to flip.

If a feasible solution exists, you only need to output one feasible solution (you do not need to minimize $ans$), but you must ensure $ans \le n \times m$.

This problem uses $\text{SPJ}$. As long as the flip operations are correct, you will get the score.

2 4
1 2 3 4
4 3 2 1

YES
1
0 2

2 4
1 2 3 4
4 1 3 2

NO

Hint

Constraints

This problem uses bundled Subtasks.

• $\texttt{Subtask \#0 (20pts)}$: At most $2$ numbers are not in their required positions.
• $\texttt{Subtask \#1 (20pts)}$: $n=2$.
• $\texttt{Subtask \#2 (20pts)}$: $m=2$.
• $\texttt{Subtask \#3 (40pts)}$: $1\le n\le 100$, $1\le m\le 100$.

All testdata satisfies $1\le n\le 100$, $1\le m\le 100$.

Translated by ChatGPT 5