Parallel Sort

题号：NC220448
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

As a master of parallel computing, schwer is recently considering about the method to achieve quick sorting on parallel computers. He needs your help!

Given a permutation $(p_1,\cdots,p_n)$ , you need to sort the permutation with minimum number of rounds. In a single round, one can take many pairs of integers $(x_1,y_1),\cdots,(x_k,y_k)$ as long as the values of $x_1,y_1,\cdots,x_k,y_k$ are pairwise distinct. Then with the help of $k$ CPUs, for each $i\in [1,k]$ , the value of $p_{x_i}$ and $p_{y_i}$ will be switched immediately. Note that a permutation $(p_1,\cdots,p_n)$ is sorted if for every integer $i\in [1,n]$ , $p_i=i$ holds.

Take some examples. Assume that $n=4$ . For $p=(1,2,3,4)$ , the minimum number of round is $0$ as it is already sorted. For $p=(4,3,2,1)$ , the answer is $1$ , as you can swap the indices $(1,4)$ and $(2,3)$ simultaneously.

输入描述:

he first line of input contains a single integer $n(1\leq n\leq 10^5)$ , indicating the length of the permutation.

The second line contains $n$ integers $p_1,...,p_n(1\leq p_i\leq n)$ , the given permutation. It is guaranteed that these integers form a permutation, that is, for every integer $i\in [1,n]$ there exists an unique integer $j\in [1,n]$ such that $p_j=i$ .

输出描述:

The first line of output should contain a single integer $m$ , the minimum number of rounds to get the permutation sorted. Then print $m$ line to show one possible solution.

The $i$ -th of the next $m$ lines should describe the $i$ -th round of your solution, beginning with a single integer $k$ , and followed by $2k$ integers $x_1,y_1;\cdots;x_k,y_k$ . The constraints that $1\leq x_i,y_i\leq n$ and the $2k$ integers are pairwise distinct must be held.

示例1

输入

复制

4
1 2 3 4

输出

复制

示例2

输入

复制

4
4 3 2 1

输出

复制

1
2 1 4 2 3