Serega the Pirate
Contest: Codeforces Round 802 (Div. 2)
Difficulty rating: 2600
Tags: brute force, constructive algorithms

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 < t_2 < \dots < 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.

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
3 3
2 1 3
6 7 4
9 8 5

Example output:
0

Example input:
2 3
1 6 4
3 2 5

Example output:
1 3

Editorial:
We need to find a simple criteria of a solvable puzzle. It can be shown that for every cell, except cell with value $$$1$$$, it should have a neighbour with a smaller value. Indeed, if the puzzle is solvable, a cell going before the first occurence of our cell always has the smaller value. Conversely, if each cell has a smaller neighbor, one can list cells one at a time, and there will always be a path to the next cell along already visited cells with lower numbers.
Let's call a cell bad, if it's value is not $$$1$$$ and it doesn't have a neighbour with a smaller value. Consider any bad cell. Let's notice, that the pair that we swap should contain either the bad cell itself, or its neighbour, otherwise that bad cell will stay bad. That way we have $$$5nm$$$ pairs of candidates, for each of which we'll run a check if the resulting puzzle is solvable.
Now we'll learn how to quickly understand, if the puzzle became solvable after a swap. For this we'll keep the amount of bad cells. After the swap, the state can be changed only for these cells and their neighbours. Let's recalc the amount of bad cells and check if it's zero.
The resulting complexity is $$$O(nm)$$$