Даны две таблицы \(A\) и \(B\) размера \(n \times m\).
Назовём сортировкой по столбцу следующее действие: выбирается столбец, и все строки упорядочиваются по значению в этом столбце, от строк, содержащих меньшие значения, к строкам с большими. В случае, если две строки имеют одинаковое значение в этом столбце, их порядок не меняется (такие сортировки называются стабильными).
Подобное поведение сортировки по столбцу можно найти практически в любом офисном приложении для работы с таблицами. Петя работает в одном из таких приложений, и у него открыта таблица \(A\). Он хочет проделать ноль или более операций сортировки по столбцу, чтобы получить таблицу \(B\).
Определите, может ли он это сделать, и если может, предложите ему алгоритм действий — последовательность столбцов, по которым нужно применить сортировку по столбцу. Обратите внимание, что не требуется минимизировать число действий.
Выходные данные
Если превратить таблицу \(A\) в таблицу \(B\) невозможно, выведите \(-1\).
В противном случае выведите \(k\) (\(0 \le k \le 5000\)) — количество сортировок, которые нужно сделать.
Затем выведите \(k\) целых чисел \(c_1, \ldots, c_k\) (\(1 \le c_i \le m\)) — номера столбцов, по которым нужно сделать сортировку.
Можно доказать, что если Петя может осуществить желаемое, то \(5000\) действий ему хватит.
Примечание
Рассмотрим второй пример. После сортировки по первому столбцу таблица имеет вид
\(\)\begin{matrix} 1&3&3\\ 1&1&2\\ 2&3&2. \end{matrix}\(\)
После того, как мы отсортируем таблицу по второму столбцу, она станет
\(\)\begin{matrix} 1&1&2\\ 1&3&3\\ 2&3&2, \end{matrix}\(\)
что нам и нужно.
В третьем тесте любая сортировка не меняет таблицу, так как все столбцы уже отсортированы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
2 2
1 2
1 2
2 2
|
1
1
|
|
2
|
3 3
2 3 2
1 3 3
1 1 2
1 1 2
1 3 3
2 3 2
|
2
1 2
|
|
3
|
2 2
1 1
2 1
2 1
1 1
|
-1
|
|
4
|
4 1
2
2
2
1
1
2
2
2
|
1
1
|