← 返回题目列表

Codeforces · 1718/E

E. 印象派

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

Burenka 有两张图片 $$$a$$$ 和 $$$b$$$,它们是相同大小 $$$n \times m$$$ 的表格。每幅画的每个单元格都有一个颜色——从 $$$0$$$ 到 $$$2 \cdot 10^5$$$ 的数字,并且两幅画的任何行或列中都没有重复的颜色,除了颜色 $$$0$$$ 之外。

Burenka 想要从图片 $$$a$$$ 中获取图片 $$$b$$$。为了实现她的目标,Burenka 可以执行 $$$2$$$ 操作之一:交换 $$$a$$$ 的任意两行或其任意两列。告诉布伦卡她是否能够实现她想要的目标,如果可以,请告诉她行动的顺序。

行从上到下编号为 $$$1$$$ 到 $$$n$$$,列从左到右编号为 $$$1$$$ 到 $$$m$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \cdot m \leq 2 \cdot 10^5$$$) — 表的大小。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含 $$$m$$$ 整数 $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ ($$$0 \leq a_{i,j} \leq 2 \cdot 10^5$$$) - 的颜色$$$i$$$-图片第 $$$a$$$ 行。保证同一行或同一列中没有相同的颜色,除了颜色$$$0$$$。

以下 $$$n$$$ 行中的第 $$$i$$$ 包含 $$$m$$$ 整数 $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, m}$$$ ($$$0 \leq b_{i,j} \leq 2 \cdot 10^5$$$) — 颜色$$$i$$$-图片第$$$b$$$行。保证同一行或同一列中没有相同的颜色,除了颜色$$$0$$$。

输出

如果无法实现 Burenka 想要的结果,则在第一行打印数字 $$$-1$$$,否则打印解决方案中的操作数 $$$k$$$ ($$$0 \le k \le 2 \cdot 10^5$$$)。可以证明,如果存在解,则存在$$$k \le 2 \cdot 10^5$$$的解。

在接下来的 $$$k$$$ 行中打印操作。首先打印操作的类型($$$1$$$ — 交换行,$$$2$$$ — 列),然后打印应用该操作的行或列的两个索引。

请注意,您不必最小化操作次数。

示例

输入 #1

3 3
1 0 2
0 0 0
2 0 1
2 0 1
0 0 0
1 0 2

输出 #1

1
1 1 3

输入 #2

4 4
0 0 1 2
3 0 0 0
0 1 0 0
1 0 0 0
2 0 0 1
0 3 0 0
0 1 0 0
0 0 1 0

输出 #2

4
1 3 4
2 3 4
2 2 3
2 1 2

输入 #3

3 3
1 2 0
0 0 0
0 0 0
1 0 0
2 0 0
0 0 0

输出 #3

-1