A permutation p of length n is a sequence of distinct integers p1,p2,...,pn (1≤pi≤n). A permutation is an identity permutation, if for any i the following equation holds pi=i.
A swap (i,j) is the operation that swaps elements pi and pj in the permutation. Let's assume that f(p) is the minimum number of swaps that you need to make the permutation p an identity permutation.
Valera wonders, how he can transform permutation p into any permutation q, such that f(q)=m, using the minimum number of swaps. Help him do that.
Output
In the first line, print integer
k − the minimum number of swaps.
In the second line, print
2k integers
x1,x2,...,x2k − the desc
ription of the swap sequence. The printed numbers show that you need to consecutively make swaps (x1,x2), (x3,x4), ..., (x2k-1,x2k).
If there are multiple sequence swaps of the minimum length, print the lexicographically minimum one.
Note
Sequence
x1,x2,...,xs is lexicographically smaller than sequence
y1,y2,...,ys, if there is such integer
r (1≤r≤s), that
x1=y1,x2=y2,...,xr-1=yr-1 and
xr<yr.