Matrix Sorting
Contest: Codeforces Round 707 (Div. 1, based on Moscow Open Olympiad in Informatics)
Difficulty rating: 2600
Tags: bitmasks, brute force, constructive algorithms, greedy, two pointers

You are given two tables $$$A$$$ and $$$B$$$ of size $$$n \times m$$$.

We define a sorting by column as the following: we choose a column and reorder the rows of the table by the value in this column, from the rows with the smallest value to the rows with the largest. In case there are two or more rows with equal value in this column, their relative order does not change (such sorting algorithms are called stable).

You can find this behavior of sorting by column in many office software for managing spreadsheets. Petya works in one, and he has a table $$$A$$$ opened right now. He wants to perform zero of more sortings by column to transform this table to table $$$B$$$.

Determine if it is possible to do so, and if yes, find a sequence of columns to sort by. Note that you do not need to minimize the number of sortings.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 1500$$$) — the sizes of the tables.

Each of the next $$$n$$$ lines contains $$$m$$$ integers $$$a_{i,j}$$$ ($$$1 \le a_{i, j} \le n$$$), denoting the elements of the table $$$A$$$.

Each of the next $$$n$$$ lines contains $$$m$$$ integers $$$b_{i, j}$$$ ($$$1 \le b_{i, j} \le n$$$), denoting the elements of the table $$$B$$$.

Output format:
If it is not possible to transform $$$A$$$ into $$$B$$$, print $$$-1$$$.

Otherwise, first print an integer $$$k$$$ ($$$0 \le k \le 5000$$$) — the number of sortings in your solution.

Then print $$$k$$$ integers $$$c_1, \ldots, c_k$$$ ($$$1 \le c_i \le m$$$) — the columns, by which Petya needs to perform a sorting.

We can show that if a solution exists, there is one in no more than $$$5000$$$ sortings.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Consider the second example. After the sorting by the first column the table becomes

$$$$$$\begin{matrix} 1&3&3\\ 1&1&2\\ 2&3&2. \end{matrix}$$$$$$

After the sorting by the second column the table becomes

$$$$$$\begin{matrix} 1&1&2\\ 1&3&3\\ 2&3&2, \end{matrix}$$$$$$

and this is what we need.

In the third test any sorting does not change anything, because the columns are already sorted.

Example input:
2 2
2 2
1 2
1 2
2 2

Example output:
1
1

Example input:
3 3
2 3 2
1 3 3
1 1 2
1 1 2
1 3 3
2 3 2

Example output:
2
1 2

Editorial:
Let's first learn how to solve with O ($$$n \cdot m^2$$$).
Note that each column can be sorted no more than once.
Now, let's note that if we could turn matrix A into matrix B, then B has a sorted column.
Idea  — we will choose the rows that we will sort from the end. To do this, we can support string equivalence classes. Where and why? If two rows are in the same class, then the columns that we applied had the same values. Then, we need to find a column that does not break the sequence between the rows inside each of the classes. Let's iterate through such a column every time. We don't care if we apply someone extra  — because of the condition of the possibility of application, it will definitely not spoil. Then just apply the column if we could. Each time, the number of equivalence classes does not decrease, so the number of columns that can be applied does not decrease. If it was not possible to sort after all the applications, it means that some of the classes could not be split correctly, which means that it is impossible to get matrix B from matrix A.
Let's learn how to solve it faster than in a cube. Let's not store equivalence classes explicitly. To do this, note that in the final state of B, the equivalence classes are sub-arrays! Then it is enough for us to store for each pair of adjacent rows whether we were able to separate them (swap the lower and upper places)  — let's call it $$$cut$$$. Also, for each column, we will store the number of still unresolved inversions in it, call it $$$cnt$$$. Initially,  — is just the number of inversions in the column. Next, it will be the same number of inversions, but only within the classes. How does this solution differ from a cube? We are able to quickly find which column can be applied - this is the column $$$j$$$ for which $$$cnt[j] = 0$$$. Then we just need to learn how to update the cnt. Let's start a queue (we can say that this is bfs, but in fact we do not use anything other than a queue from bfs), to which we will add only columns $$$j$$$ in which $$$cnt[j] = 0$$$, apply sorting by column, update cnt and add new columns that have $$$cnt=0$$$. $$$cut$$$will help us with this. Let's, if we managed to swap the columns (that is, in the current column $$$v$$$, $$$b[i][v] < b[i - 1][v]$$$), set $$$cut[i] = 1$$$ and update all the values of $$$cnt$$$ through this row. It is clear that it does not make sense to split rows twice. Since we will apply each column at most once, and the pairs of adjacent rows are $$$O(n)$$$, the time complexity is $$$O (n \cdot m)$$$. Do not forget that it is not necessary to divide into exactly $$$n$$$ equivalence classes, because a smaller number may be enough. So in the end, check transformations(not difficult, but need to be careful).
There is also a solution with time complexity $$$O(nm log)$$$, but I think, it is more difficult both in terms of understanding and implementation.