B. Пакетная сортировка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана таблица, состоящая из n строк и m столбцов.

Числа в каждой строке образуют перестановку от чисел 1 до m.

Разрешается не более одного раза для каждой строки поменять в ней два числа местами. Также разрешается не более одного раза поменять местами два столбца целиком. Таким образом, суммарно можно совершить от 0 до n + 1 действия. Описанные действия можно выполнять в любом порядке.

Проверьте, можно ли с помощью указанных действий добиться ситуации, чтобы в каждой строке была записана тождественная перестановка 1, 2, ..., m. Другими словами, существует ли такая последовательность действий, в результате которой числа в каждой из строк будут отсортированы по возрастанию.

Входные данные

В первой строке входных данных записаны два числа n и m (1 ≤ n, m ≤ 20) — количество строк и столбцов в заданной таблице.

В следующих n строках записаны по m чисел — содержимое таблицы. Гарантируется, что числа в каждой строке образуют перестановку чисел от 1 до m.

Выходные данные

Выведите «YES» (без кавычек), если с помощью указанных действий можно получить тождественную перестановку одновременно во всех строках таблицы. В противном случае выведите «NO» (без кавычек).

Примеры
Входные данные
2 4
1 3 2 4
1 3 4 2
Выходные данные
YES
Входные данные
4 4
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
Выходные данные
NO
Входные данные
3 6
2 1 3 4 5 6
1 2 4 3 5 6
1 2 3 4 6 5
Выходные данные
YES
Примечание

В первом примере можно действовать следующим образом:

  1. Сначала поменять местами второй и третий столбец. После этого действия таблица будет выглядеть так:
    1 2 3 4
    1 4 3 2
  2. Затем во второй строке поменять местами числа на второй и четвёртой позиции. После этого действия таблица будет выглядеть так:
    1 2 3 4
    1 2 3 4