CF1044E.Grid Sort

You are given an $n \times m$ grid. Each grid cell is filled with a unique integer from $1$ to $nm$ so that each integer appears exactly once.

In one operation, you can choose an arbitrary cycle of the grid and move all integers along that cycle one space over. Here, a cycle is any sequence that satisfies the following conditions:

• There are at least four squares.
• Each square appears at most once.
• Every pair of adjacent squares, and also the first and last squares, share an edge.

For example, if we had the following grid:

We can choose an arbitrary cycle like this one:

To get the following grid:

In this particular case, the chosen cycle can be represented as the sequence $[1, 2, 3, 6, 5, 8, 7, 4]$, the numbers are in the direction that we want to rotate them in.

Find any sequence of operations to sort the grid so that the array created by concatenating the rows from the highest to the lowest is sorted (look at the first picture above).

Note you do not need to minimize number of operations or sum of cycle lengths. The only constraint is that the sum of all cycles lengths must not be greater than $10^5$. We can show that an answer always exists under the given constraints. Output any valid sequence of moves that will sort the grid.

你被给定一个 $n \times m$ 的网格。每个网格单元格中填入 $1$ 到 $nm$ 之间的唯一整数，且每个整数恰好出现一次。

在一次操作中，你可以任选网格中的一个环，并将该环上所有整数沿此环同向移动一格。此处，“环”指满足以下条件的任意序列：

• 至少包含四个方格；
• 每个方格至多出现一次；
• 序列中每一对相邻方格（包括首尾两个方格）必须共享一条边。

例如，若初始网格如下所示：

我们可以任选如下环：

从而得到如下网格：

在本例中，所选环可表示为序列 $[1, 2, 3, 6, 5, 8, 7, 4]$，其中数字顺序即为我们希望旋转的方向。

请找出任意一组操作序列，使得最终网格被排序：即按从上到下、从左到右的顺序将所有行拼接成一个一维数组后，该数组严格递增（参见上方第一张图）。

注意：你无需最小化操作次数或所有环长度之和。唯一约束是：所有环的长度总和不得超过 $10^5$。可以证明，在给定约束下，答案恒存在。请输出任意一组能将网格排序的有效操作序列。

The first line contains two integers $n$ and $m$ ($3 \leq n,m \leq 20$) — the dimensions of the grid.

Each of the next $n$ lines contains $m$ integers $x_{i,1}, x_{i,2}, \ldots, x_{i, m}$ ($1 \leq x_{i,j} \leq nm$), denoting the values of the block in row $i$ and column $j$.

It is guaranteed that all $x_{i,j}$ are distinct.

第一行包含两个整数 $n$ 和 $m$（$3 \leq n,m \leq 20$）——表示网格的维度。

接下来的 $n$ 行中，每行包含 $m$ 个整数 $x_{i,1}, x_{i,2}, \ldots, x_{i, m}$（$1 \leq x_{i,j} \leq nm$），表示第 $i$ 行第 $j$ 列方块的数值。

保证所有 $x_{i,j}$ 互不相同。

First, print a single integer $k$, the number of operations ($k \geq 0$).

On each of the next $k$ lines, print a cycle as follows:

$$s\\ y\_1\\ y\_2\\ \\ldots\\ y\_s$$

Here, $s$ is the number of blocks to move ($s \geq 4$). Here we have block $y_1$ moving to where block $y_2$ is, block $y_2$ moving to where block $y_3$ is, and so on with block $y_s$ moving to where block $y_1$ is.

The sum of $s$ over all operations must be at most $10^5$.

首先，输出一个整数 $k$，表示操作次数（$k \geq 0$）。

接下来的 $k$ 行中，每行输出一个循环，格式如下：

$$s\\ y\_1\\ y\_2\\ \\ldots\\ y\_s$$

其中，$s$ 是要移动的块的数量（$s \geq 4$）。此处表示块 $y_1$ 移动到块 $y_2$ 的位置，块 $y_2$ 移动到块 $y_3$ 的位置，依此类推，块 $y_s$ 移动到块 $y_1$ 的位置。

所有操作中 $s$ 的总和至多为 $10^5$。

The first sample is the case in the statement. Here, we can use the cycle in reverse order to sort the grid.

第一个样例即为题目描述中的情况。在此情况下，我们可以逆序使用该循环来对网格进行排序。