← 返回题目列表

Codeforces · 1700/E

E. 海盗塞雷加

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

小海盗塞雷加用不同种类的谜题抢劫了一艘船。在所有种类中,他只喜欢一种,最难的一种。

拼图是一个由 $$$n$$$ 行和 $$$m$$$ 列组成的表格,其单元格包含从 $$$1$$$ 到 $$$n \cdot m$$$ 的每个数字恰好一次。

要解决难题,您必须在表中找到一系列单元格,使得任意两个连续的单元格在表中的一侧相邻。该序列可以具有任意长度,并且应该访问每个单元一次或多次。对于包含数字 $$$i$$$ 的单元格,将该单元格在序列中第一次出现的位置表示为 $$$t_i$$$。如果 $$$t_1 < t_2 < \dots < t_{nm}$$$,则该序列解决了难题。换句话说,对于每个 $$$x$$$,应该先访问编号为 $$$x$$$ 的单元格,然后再访问编号为 $$$x + 1$$$ 的单元格。

如果存在至少一个合适的序列,我们就称这个谜题是可解的。

Serega 可以一步选择表格中的两个任意单元格(不一定是相邻的)并交换它们的数字。他想知道解开谜题所需的最少步数,但他太不耐烦了。因此,请说明最小移动次数是 $$$0$$$、$$$1$$$ 还是至少 $$$2$$$。如果需要 $$$1$$$ 移动,请同时找到适合交换的单元对的数量。

输入

第一行有两个正数 $$$n, m$$$ ($$$1 \leq n\cdot m \leq 400\,000$$$) — 表格尺寸。

在接下来的 $$$n$$$ 行中,有 $$$m$$$ 整数 $$$a_{i1}, a_{i2}, \dots, a_{im}$$$ ($$$1 \le a_{ij} \le nm$$$)。

保证从 $$$1$$$ 到 $$$nm$$$ 的每个数字在表中恰好出现一次。

输出

设 $$$a$$$ 为使谜题可解的最小步数。

如果 $$$a = 0$$$,则打印 $$$0$$$。

如果 $$$a = 1$$$,则打印 $$$1$$$ 和有效交换次数。

如果 $$$a \ge 2$$$,则打印 $$$2$$$。

示例

输入 #1

3 3
2 1 3
6 7 4
9 8 5

输出 #1

0

输入 #2

2 3
1 6 4
3 2 5

输出 #2

1 3

输入 #3

1 6
1 6 5 4 3 2

输出 #3

2

注意

在第一个示例中,序列 $$$(1, 2), (1, 1), (1, 2), (1, 3), (2, 3), (3, 3)$$$, $$$(2, 3), (1, 3), (1, 2), (1, 1), (2, 1), (2, 2), (3, 2), (3, 1)$$$ 解决了这个难题,所以答案是 $$$0$$$。

第二个示例中的难题无法解决,但在对值为 $$$(1, 5)、(1, 6)、(2, 6)$$$ 的单元格进行 3 次交换后即可解决。

第三个示例中的谜题需要至少两次交换,因此答案是 $$$2$$$。