Grid Permutation

You are given an n x m grid where each cell contains an integer representing a type of crop. You are allowed to permute (i.e. rearrange) the entries of the grid arbitrarily. Your task is to determine whether it is possible to rearrange the grid so that no two adjacent cells (cells that share an edge) contain the same crop type.

A key observation is that if any crop type appears too many times in a row or a column, then even after an optimal rearrangement, you might not be able to separate them enough. More formally, for any row, if the maximum frequency of any crop is greater than \( \lceil m/2 \rceil \), or for any column if the maximum frequency of any crop is greater than \( \lceil n/2 \rceil \), then such a permutation is impossible.

Given this, output YES if such a rearrangement exists and NO otherwise.

inputFormat

The first line contains two integers n and m (the number of rows and columns, respectively).

The following n lines each contain m space-separated integers representing the grid.

outputFormat

Output a single line containing YES if it is possible to permute the grid such that no two adjacent cells have the same crop type, otherwise output NO.

3 3
1 2 3
2 3 1
3 1 2

YES