Serega the Pirate

题意翻译

一个 $n \times m$ 的表格中填入了 $1,2,...,n \times m$ 的所有数恰一次。 称一种填法可解，当可以找出一条路径，它第一次到达每个格子的顺序与格内所填的数同序。换言之，这条路径应该先经过 $x$，再经过 $x+1$。路径的起点，终点，长度任意，可以重复经过同一个格子。 问对给定的填法，至少需要交换几对格子，才能使填法可解。若最小值为 $0$，输出 $0$；若最小值为 $1$，输出 $1$ 和交换方法数；若最小值大于 $1$，输出 $2$。 数据范围：$n \times m \le 400000$。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #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

说明

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

**题目大意：**
一个 $n \times m$ 的表格中填入了 $1,2,...,n \times m$ 的所有数恰好一次。如果存在一条路径，它第一次到达每个格子的顺序与格内所填的数同序，则称这种填法可解。路径的起点、终点、长度任意，可以重复经过同一个格子。需要求出对给定的填法，至少需要交换几对格子，才能使填法可解。如果最小值为 $0$，输出 $0$；如果最小值为 $1$，输出 $1$ 和交换方法数；如果最小值大于 $1$，输出 $2$。

**输入输出数据格式：**
- **输入格式：**
- 第一行包含两个正整数 $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
```**题目大意：** 一个 $n \times m$ 的表格中填入了 $1,2,...,n \times m$ 的所有数恰好一次。如果存在一条路径，它第一次到达每个格子的顺序与格内所填的数同序，则称这种填法可解。路径的起点、终点、长度任意，可以重复经过同一个格子。需要求出对给定的填法，至少需要交换几对格子，才能使填法可解。如果最小值为 $0$，输出 $0$；如果最小值为 $1$，输出 $1$ 和交换方法数；如果最小值大于 $1$，输出 $2$。 **输入输出数据格式：** - **输入格式：** - 第一行包含两个正整数 $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 ```