CF1700E Serega the Pirate

小海盗 Serega 抢劫了一艘装满各种谜题的船。在所有类型中，他只喜欢一种，最难的那种。 一个谜题是一个 $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 \geq 2$，输出 $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$。 由 ChatGPT 4.1 翻译