CF1700E.Serega the Pirate

Little pirate Serega robbed a ship with puzzles of different kinds. Among all kinds, he liked only one, the hardest.

A puzzle is a table of $n$ rows and $m$ columns, whose cells contain each number from $1$ to $n \cdot m$ exactly once.

To solve a puzzle, you have to find a sequence of cells in the table, such that any two consecutive cells are adjacent by the side in the table. The sequence can have arbitrary length and should visit each cell one or more times. For a cell containing the number $i$, denote the position of the first occurrence of this cell in the sequence as $t_i$. The sequence solves the puzzle, if $t_1 \lt t_2 \lt \dots \lt t_{nm}$. In other words, the cell with number $x$ should be first visited before the cell with number $x + 1$ for each $x$.

Let's call a puzzle solvable, if there exists at least one suitable sequence.

In one move Serega can choose two arbitrary cells in the table (not necessarily adjacent by the side) and swap their numbers. He would like to know the minimum number of moves to make his puzzle solvable, but he is too impatient. Thus, please tell if the minimum number of moves is $0$, $1$, or at least $2$. In the case, where $1$ move is required, please also find the number of suitable cell pairs to swap.

小海盗谢尔加抢劫了一艘装有各种谜题的船。在所有种类中，他只喜欢一种，也是最难的一种。

一个谜题是一个 $n$ 行 $m$ 列的表格，其中每个从 $1$ 到 $n \cdot m$ 的整数恰好出现一次。

要解开一个谜题，你需要在表格中找到一个格子序列，使得序列中任意两个相邻格子在表格中必须是上下左右相邻（即共享一条边）。该序列长度可以任意，并且每个格子可以被访问一次或多次。对于包含数字 $i$ 的格子，记其在序列中首次出现的位置为 $t_i$。若对所有 $x$，均有 $t_1 \lt t_2 \lt \dots \lt t_{nm}$，则该序列可解此谜题。换言之，对每个 $x$，含数字 $x$ 的格子必须在含数字 $x + 1$ 的格子之前首次被访问。

若存在至少一个满足上述条件的序列，则称该谜题可解。

谢尔加每次操作可任选表格中两个格子（不必相邻），并交换它们所含的数字。他想知道使该谜题变为可解所需的最少操作次数，但他又太没耐心。因此，请你判断：最少操作次数是 $0$、$1$，还是至少为 $2$。若最少操作次数恰为 $1$，还需进一步求出有多少对格子满足交换后谜题可解。

In the first line there are two whole positive numbers $n, m$ ($1 \leq n\cdot m \leq 400\,000$) — table dimensions.

In the next $n$ lines there are $m$ integer numbers $a_{i1}, a_{i2}, \dots, a_{im}$ ($1 \le a_{ij} \le nm$).

It is guaranteed that every number from $1$ to $nm$ occurs exactly once in the table.

第一行包含两个正整数 $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$ 之间的每个整数在表格中恰好出现一次。

Let $a$ be the minimum number of moves to make the puzzle solvable.

If $a = 0$, print $0$.

If $a = 1$, print $1$ and the number of valid swaps.

If $a \ge 2$, print $2$.

设 $a$ 为使该谜题可解所需的最少移动次数。

若 $a = 0$，输出 $0$。

若 $a = 1$，输出 $1$ 和有效的交换次数。

若 $a \ge 2$，输出 $2$。

In the first example the sequence $(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)$ solves the puzzle, so the answer is $0$.

The puzzle in the second example can't be solved, but it's solvable after any of three swaps of cells with values $(1, 5), (1, 6), (2, 6)$.

The puzzle from the third example requires at least two swaps, so the answer is $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)$ 的任意一个单元格对之后即可求解。

第三个例子中的谜题至少需要两次交换，因此答案为 $2$。