← 返回题目列表

Codeforces · 1500/C

C. 矩阵排序

中文机器翻译题面 查看原题

给你两个表 $$$A$$$ 和 $$$B$$$,大小为 $$$n \times m$$$。

我们定义按列排序如下:我们选择一列,并根据该列中的值对表的行重新排序,从具有最小值的行到具有最大值的行。如果该列中有两行或更多行具有相同的值,则它们的相对顺序不会改变(这种排序算法称为稳定)。

您可以在许多用于管理电子表格的办公软件中找到这种按列排序的行为。 Petya 在其中一间工作,他现在开了一张桌子$$$A$$$。他想要按列执行零次或多次排序,以将该表转换为表 $$$B$$$。

确定是否可以这样做,如果可以,则找到要排序的列序列。请注意,您不需要最小化排序次数。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 1500$$$) — 表格的大小。

接下来的 $$$n$$$ 行包含 $$$m$$$ 整数 $$$a_{i,j}$$$ ($$$1 \le a_{i, j} \le n$$$),表示表 $$$A$$$ 的元素。

接下来的 $$$n$$$ 行包含 $$$m$$$ 整数 $$$b_{i, j}$$$ ($$$1 \le b_{i, j} \le n$$$),表示表 $$$B$$$ 的元素。

输出

如果无法将 $$$A$$$ 转换为 $$$B$$$,则打印 $$$-1$$$。

否则,首先打印一个整数 $$$k$$$ ($$$0 \le k \le 5000$$$) — 解决方案中的排序次数。

然后打印 $$$k$$$ 整数 $$$c_1, \ldots, c_k$$$ ($$$1 \le c_i \le m$$$) - Petya 需要执行排序的列。

我们可以证明,如果存在解决方案,则在不超过 $$$5000$$$ 排序中存在一个解决方案。

示例

输入 #1

2 2
2 2
1 2
1 2
2 2

输出 #1

1
1

输入 #2

3 3
2 3 2
1 3 3
1 1 2
1 1 2
1 3 3
2 3 2

输出 #2

2
1 2

输入 #3

2 2
1 1
2 1
2 1
1 1

输出 #3

-1

输入#4

4 1
2
2
2
1
1
2
2
2

输出#4

1
1

注意

考虑第二个例子。按第一列排序后,表格变为

$$$$$$\begin{矩阵} 1&3&3\\ 1&1&2\\ 2&3&2。 \end{矩阵}$$$$$$

按第二列排序后,表格变为

$$$$$$\begin{矩阵} 1&1&2\\ 1&3&3\\ 2&3&2, \end{矩阵}$$$$$$

这就是我们所需要的。

在第三个测试中,任何排序都不会改变任何内容,因为列已经排序。