小海盗塞雷加用不同种类的谜题抢劫了一艘船。在所有种类中,他只喜欢一种,最难的一种。
拼图是一个由 $$$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$$$。