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
#include<cstdio>
#include<vector>
#include<map>
#include<utility>
#include<iostream>
#include<algorithm>
#include<list>

using namespace std;

int main(){
//printf("2\n5\n5 6 1 4 3\n4\n1 2 3 4");
//return 0;
int n;
int t;
int x,y;
vector<pair<int, int>> v;
v.push_back({0,0});

scanf("%d", &n);
for(int i=1; i<=n; i++){
    scanf("%d", &t);
    v.push_back({t, i});
}

sort(v.begin(), v.end());

list<vector<int>> all_cykles;

for(int i = 1; i<=n; i++){
    int act;
    if(i == v[i].second)
        continue;
    if(v[i].first == 0)
        continue;
    v[i].first = 0;
    act = v[i].second;
    vector<int> cykle = {i};
    while( act != i){
        v[act].first = 0;
        cykle.push_back(act);
        act = v[act].second;    
    }
    /*
    printf("Cykle :\n");
    for (auto r: cykle)
        printf("%d ", r);*/
    all_cykles.push_front(cykle);   
}
    
if (all_cykles.empty()){
    printf("0\n");
    return 0;
}
list<int> iter_list = {}; 
list<int> iter_list2 = {}; 
for(auto &a: all_cykles){
   if(a.size() == 2){
       iter_list.push_front(a[0]);
       iter_list.push_back(a[1]);
       continue;
   }
   n = a.size();
   for(int i=1; i <= (n-1)/2; i++){   
      iter_list.push_front(a[(n-1)/2-i]);
      iter_list.push_back( a[(n-1)/2+i]);
      iter_list2.push_front(a[(n-1)/2-i]);
      iter_list2.push_back(a[(n-1)/2+i-1]);      
   }
   if (n%2==0){
      iter_list2.push_front(a[(n-1)]);
      iter_list2.push_back(a[(n-2)]);
   }
}

if (iter_list2.empty()){
    printf("1\n%ld\n", iter_list.size());
    for (auto i: iter_list)
        printf("%d ", i);
   // printf("\n");
    }
else{
    printf("2\n%ld\n", iter_list.size());
    for (auto i: iter_list)
        printf("%d ", i);
    printf("\n%ld\n", iter_list2.size());
    for (auto i: iter_list2)
        printf("%d ", i);
}


}