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
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>

#define ll long long
#define fors(u, n, s) for(ll u=(s); u < (n); u++)
#define foru(u, n) fors(u, n, 0)
#define ir(a, b, x) (((a) <= (x)) && ((x) <= (b)))
#define vec vector
#define pb push_back

using namespace std;

#define N 3000

int arr[N];
int inv_arr[N];
int n;

void normalize(){
    int to_use = 0;
    foru(i, N+1){
        foru(j, n){
            if(arr[j]==i){
                arr[j]=to_use;
                to_use++;
            }
        }
    }
}

int mapA[N];
int mapB[N];

void make_path(int x, int y){
    int z = arr[x];
    mapA[x]=y;
    mapB[y]=z;

    ///A(x)=y => A(y)=x
    if(mapA[y]==-1) make_path(y, x);

    ///B(y)=z => B(z)=y
    if(mapB[z]==-1){
        mapB[z]=y;
        make_path(inv_arr[y], z);
    }
}

bool visited[N];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    foru(i, n) cin >> arr[i];
    normalize();

    foru(i, n) inv_arr[arr[i]]=i;

    bool true_simple=true;
    foru(i, n) if(arr[i]!=i) true_simple=false;

    if(true_simple){cout << 0; return 0;}

    bool simple=true;
    foru(i, n) if(arr[arr[i]]!=i) simple=false;

    if(simple){
        cout << 1 << endl;

        vec<int> f;
        vec<int> s;

        foru(i, n) visited[i]=false;
        foru(i, n){
            if(arr[i]==i) continue;
            if(visited[i]) continue;
            f.pb(i); s.pb(arr[i]);
            visited[i]=true; visited[arr[i]]=true;
        }
        cout << 2*f.size() << endl;
        for(int i=0; i<f.size(); i++) cout << f[i]+1 << " ";
        for(int i=s.size()-1; i>=0; i--) cout << s[i]+1 << " ";
        return 0;
    }

    foru(i, n) {mapA[i]=-1; mapB[i]=-1;}

    foru(i, n){ ///i pos
        if(mapA[i]!=-1) continue;
        make_path(i, arr[i]);
    }

    cout << 2 << endl;

    vec<int> f;
    vec<int> s;

    foru(i, n) visited[i]=false;
    foru(i, n){
        if(mapA[i]==i) continue;
        if(visited[i]) continue;
        f.pb(i); s.pb(mapA[i]);
        visited[i]=true; visited[mapA[i]]=true;
    }
    cout << 2*f.size() << endl;
    for(int i=0; i<f.size(); i++) cout << f[i]+1 << " ";
    for(int i=s.size()-1; i>=0; i--) cout << s[i]+1 << " ";
    cout << endl;
    f.resize(0);
    s.resize(0);

    foru(i, n) visited[i]=false;
    foru(i, n){
        if(mapB[i]==i) continue;
        if(visited[i]) continue;
        f.pb(i); s.pb(mapB[i]);
        visited[i]=true; visited[mapB[i]]=true;
    }
    cout << 2*f.size() << endl;
    for(int i=0; i<f.size(); i++) cout << f[i]+1 << " ";
    for(int i=s.size()-1; i>=0; i--) cout << s[i]+1 << " ";
    cout << endl;
    f.resize(0);
    s.resize(0);

    return 0;
}