Вам задана таблица, состоящая из n строк и m столбцов.
Числа в каждой строке образуют перестановку от чисел 1 до m.
Разрешается не более одного раза для каждой строки поменять в ней два числа местами. Также разрешается не более одного раза поменять местами два столбца целиком. Таким образом, суммарно можно совершить от 0 до n + 1 действия. Описанные действия можно выполнять в любом порядке.
Проверьте, можно ли с помощью указанных действий добиться ситуации, чтобы в каждой строке была записана тождественная перестановка 1, 2, ..., m. Другими словами, существует ли такая последовательность действий, в результате которой числа в каждой из строк будут отсортированы по возрастанию.
Выходные данные
Выведите «YES» (без кавычек), если с помощью указанных действий можно получить тождественную перестановку одновременно во всех строках таблицы. В противном случае выведите «NO» (без кавычек).
Примечание
В первом примере можно действовать следующим образом:
- Сначала поменять местами второй и третий столбец. После этого действия таблица будет выглядеть так: 1 2 3 4 1 4 3 2
- Затем во второй строке поменять местами числа на второй и четвёртой позиции. После этого действия таблица будет выглядеть так: 1 2 3 4 1 2 3 4
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 4
1 3 2 4
1 3 4 2
|
YES
|
|
2
|
4 4
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
|
NO
|
|
3
|
3 6
2 1 3 4 5 6
1 2 4 3 5 6
1 2 3 4 6 5
|
YES
|