给你一个 $$$n \times m$$$ 网格。每个网格单元都填充从 $$$1$$$ 到 $$$nm$$$ 的唯一整数,以便每个整数只出现一次。
在一次操作中,您可以选择网格的任意循环,并将所有整数沿着该循环移动一个空格。这里,循环是满足以下条件的任何序列:
- 至少有四个方块。
- 每个方块最多出现一次。
- 每对相邻的方块以及第一个和最后一个方块共享一条边。
例如,如果我们有以下网格:
我们可以选择一个任意周期,如下所示:
获得以下网格:
在这种特殊情况下,所选的循环可以表示为序列 $$$[1, 2, 3, 6, 5, 8, 7, 4]$$$,数字的方向是我们想要旋转的方向。
找到对网格进行排序的任意操作序列,以便对通过从最高到最低连接行创建的数组进行排序(参见上面的第一张图片)。
请注意,您不需要最小化操作数量或循环长度总和。唯一的限制是所有循环长度的总和不得大于 $$$10^5$$$。我们可以证明在给定的约束下答案总是存在的。输出对网格进行排序的任何有效的移动序列。
输入
第一行包含两个整数 $$$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}$$$ 都是不同的。
输出
首先,打印单个整数 $$$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$$$。
示例
输入 #1
3 3 4 1 2 7 6 3 8 5 9
输出 #1
1 8 1 4 7 8 5 6 3 2
输入 #2
3 5 1 2 3 5 10 11 6 4 14 9 12 7 8 13 15
输出 #2
3 4 4 14 13 8 4 5 10 9 4 4 12 7 6 11
注意
第一个样本是语句中的情况。这里,我们可以使用逆序循环来对网格进行排序。