Matrix Flip Transformation

In this problem, you are given an even-numbered matrix with ( n ) rows and ( m ) columns. The matrix does not necessarily contain exactly ( n ) copies of each number ( 1, 2, \dots, m ). Kid is allowed to perform the following two kinds of operations any number of times:

1. Choose any row and reverse the order of its elements.
2. Choose any column and reverse the order of its elements (i.e. flip the column top‐to‐bottom).

A row reversal operation on row ( i ) will transform the row ( [a_{i,1}, a_{i,2}, \dots, a_{i,m}] ) into ( [a_{i,m}, a_{i,m-1}, \dots, a_{i,1}] ). Similarly, a column reversal on column ( j ) reverses the order of the elements in that column.

By applying a sequence of such operations, the goal is to transform the matrix into the following form:

[ \begin{array}{cccc} 1 & 2 & \cdots & m \ 1 & 2 & \cdots & m \ \vdots & \vdots & \ddots & \vdots \ 1 & 2 & \cdots & m \end{array} ]

That is, every row should become ( [1, 2, 3, \dots, m] ). Note that both ( n ) and ( m ) are even.

Your task is to decide whether it is possible to obtain the target matrix from the given matrix by performing an arbitrary number of these operations. You only need to output the answer (i.e. print “YES” if possible and “NO” otherwise); the actual sequence of operations is not required.

Hint: Since each row and each column can be flipped at most once (flipping twice has no effect), you essentially have two binary choices for each row and each column. If we denote a row flip by a flag ( r_i ) (where ( r_i = 0 ) means no flip and ( r_i = 1 ) means flip) and similarly ( c_j ) for columns, then after applying the operations, the element that ends up in row ( i ) and column ( j ) comes from:

[ A\Big[, i' ,, j' \Big] \quad\text{where}\quad i' = \begin{cases} i, & c_j = 0,\ n-i+1, & c_j = 1, \end{cases}\qquad j' = \begin{cases} j, & r_i = 0,\ m-j+1, & r_i = 1. \end{cases} ]

This entry must equal ( j ) (or ( j+1 ) in 1-indexed form) for the final matrix to be correct. Decide if there exist assignments for ( {r_i} ) and ( {c_j} ) making this true for every ( i, j ).

inputFormat

The first line contains two even integers ( n ) and ( m ). Then follow ( n ) lines, each containing ( m ) integers representing the matrix. The ( j )th integer of a row is the value ( a_{i,j} ).

outputFormat

Output a single line containing the string “YES” if it is possible to transform the matrix into the target form, and “NO” otherwise.

sample

2 2
1 2
1 2

YES