[AdditionalFile5388.zip](file://AdditionalFile5388.zip?type=additional_file)

#5388. 「OOI 2021 Day 1」矩阵排序

标签: 传统 | 时间限制: 2500 ms | 内存限制: 256 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2021 Day1 T4 「Сортировка матрицы」。

给定两个大小为 $n \times m$ 的表格 $A$ 和 $B$。

我们将“按列排序”定义为以下操作：选择一列，并根据该列的值对所有行进行排序，从包含较小值的行到包含较大值的行。如果两行在该列的值相同，则它们的相对顺序保持不变（这种排序称为「稳定排序」）。

这种按列排序的功能几乎可以在任何用于处理表格的办公应用程序中找到。皮特正在使用其中一款应用程序，他打开了表格 $A$。他希望通过零次或多次按列排序操作，将表格 $A$ 转换为表格 $B$。

请确定他是否能做到这一点，如果可以，请为他提供一个操作算法——即按列排序的列序号序列。注意，不需要最小化操作次数。

输入格式

第一行包含两个整数 $n$ 和 $m$ $(1 \leq n, m \leq 2000)$，表示表格的尺寸。

接下来的 $n$ 行，每行包含 $m$ 个整数 $a_{i,j}$ $(1 \leq a_{i,j} \leq n)$，定义表格 $A$。

再接下来的 $n$ 行，以相同格式定义表格 $B$，每行包含 $m$ 个整数 $b_{i,j}$ $(1 \leq b_{i,j} \leq n)$。

输出格式

如果无法通过排序将表格 $A$ 转换为表格 $B$，则输出 -1。

否则，第一行输出一个整数 $k$ $(0 \leq k \leq 5000)$，表示需要进行的排序次数。

接下来一行输出 $k$ 个整数 $c_1, \ldots, c_k$ $(1 \leq c_i \leq m)$，表示需要按其排序的列序号。

可以证明，如果皮特能够实现目标，那么 $5000$ 次操作足够完成。

样例 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

以第二个样例为例。按第一列排序后，表格变为：

$$\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}$$

这正是我们需要的表格 $B$。

样例 3

输入

2 2
1 1
2 1
2 1
1 1

输出

-1

在第三个样例中，任何排序操作都不会改变表格，因为所有列已经有序。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。

子任务	分值	附加限制	子任务依赖	备注
$1$	$6$	$n \leq 6$，$m \leq 6$	$0$
$2$	$4$			表格 $A$ 和 $B$ 的所有列均为 $1$ 到 $n$ 的排列
$3$	$16$	$n \leq 500$，$m \leq 6$	$0, 1$
$4$	$10$	$n \leq 100$，$m \leq 100$	$0, 1$
$5$	$15$	$n \leq 500$，$m \leq 500$	$0, 1, 3, 4$
$6$	$18$	$n \leq 1000$，$m \leq 1000$	$0, 1, 3, 4, 5$
$7$	$31$	$n \leq 2000$，$m \leq 2000$	$0 \sim 6$