1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>

int B[3000], N[3000], P[3000], U[3000], S[3000];

int main()
{
  int n, i, j, k, h, c, r, p, x, y;
  for (h=0; h<3000; h++) B[h]=-1;
  scanf("%i", &n);
  for (i=0; i<n; i++) scanf("%i", &h), B[h-1]=i;
  for (h=0, i=0; h<3000; h++) if (B[h]>-1) N[B[h]]=i++, P[N[B[h]]]=B[h];

  for (c=0, r=1; r; c++)
  {
    for (i=0; i<n; i++) U[i]=1;
    for (i=0, p=0; i<n; i++)
    {
      for (j=i, k=P[j]; U[j] && U[k]; j=x, k=P[k])
      {
        U[j]=0, U[k]=0;
        if (j==k) break;
        S[p++]=j;
        S[p++]=k;
        x=N[j], y=N[k];
        N[j]=y, N[k]=x;
        P[y]=j, P[x]=k;
      }
    }
    for (i=0, r=0; i<n; i++) r+=N[i]!=i;
    if (!c) printf("%i\n", (r>0)+(p>0));
    if (!p) break;
    printf("%i\n", p);
    for (i=0;   i<p; i+=2) printf("%i ",  S[i]+1);
    for (i=p-1; i>0; i-=2) printf("%i%c", S[i]+1, "\n "[i-2>0]);
  }
  return 0;
}