Skip to content

1296: Shuffle

题目

题目描述

给定一个长度为 $n$ 的排列,元素标号为 $1 \dots n$。你需要若干次操作将这个排列排序为 $1, 2, \dots, n$,每次一操作是一系列“并行的”交换:你可以选择若干个不相交的元素对,将他们分别交换。

请构造一种方案,使得操作的次数尽可能少。

Input

请从 stdin 读入。

输入第一行一个正整数 $n (1 \leq n \leq 10 ^ 5)$ 。对于 $90$ 分的数据,$n \leq 9$。

第二行包含 $n$ 个空格隔开整数表示排列,第 $i$ 个数为排列第 $i$ 位 $a_i (1 \leq a_i \leq n)$。输入保证 $n$ 个数互不相同。

Output

请输出到 stdout 中。

输出第一行为你的操作次数 $m$。

接下来 $m$ 行,每行第一个数 $k_i$ 表示第 $i$ 次操作交换的对数,接下来 $2 k_i$ 个整数,每两个代表一对待交换元素的下标。由于元素对不相交,你需要保证这 $2 k_i$ 个整数互不相同,且在 $[1, n]$ 内。

如果有多种方案,输出任意一种即可。注意,你仅需最小化 $m$,并不需要最小化 $\sum k_i$。

Sample Input

txt 4 1 2 3 4

txt 4 4 3 2 1

txt 3 2 3 1

txt 4 2 3 4 1

Sample Output

txt 0

txt 1 2 1 4 2 3

txt 2 1 2 3 1 1 2

txt 2 2 1 2 3 4 1 1 3

Constraints

Time Limit: 1s

Memory Limit: 128MB

Note

在合理范围内的行末空格与文末回车会被忽略掉(过长可能触发输出长度限制)。因此,对于第一组数据来说,如下输出也是正确的。

```txt 0

``` 请注意输出的是下标而不是元素,你可以参考最后一组样例输出来确认一下。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!