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
|
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &a){
T w=1; a=0;
char ch=getchar();
for(;ch < '0' || ch > '9';ch=getchar()) if(ch == '-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) a=(a<<3)+(a<<1)+(ch^48);
a*=w;
}
template <typename T> inline void ckmax(T &a, T b){a = a > b ? a : b;}
template <typename T> inline void ckmin(T &a, T b){a = a < b ? a : b;}
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define Debug(x) cout << #x << " = " << x << endl
#define For(i,l,r) for (int i = l; i <= r; ++i)
#define foR(i,l,r) for (int i = l; i >= r; --i)
const int N = 1e5 + 10;
struct edge {
int to, nxt;
} e[N << 1], edges[N << 1];
int head[N], cnt;
int Head[N], cnts;
inline void add (int u, int v) {
e[++cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt;
}
inline void addedge (int u, int v) {
edges[++cnts].to = v; edges[cnts].nxt = Head[u]; Head[u] = cnts;
}
int sta[N], top, dfn[N], low[N], deep;
int vis[N], color, col[N];
int node[N];
void tarjan (int u) {
dfn[u] = low[u] = ++deep;
vis[sta[++top] = u] = 1;
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (!dfn[v]) tarjan(v), ckmin(low[u], low[v]);
else if (vis[v]) ckmin(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
color++;
node[color] = u;
while (sta[top] != u) {
col[sta[top]] = color;
vis[sta[top--]] = 0;
}
col[sta[top]] = color;
vis[sta[top--]] = 0;
}
}
int du[N], rd[N];
int g[N], tot;
vi tr[N];
void dfs (int u) {
int fl = 0;
for (int i = Head[u]; i; i = edges[i].nxt) {
int v = edges[i].to;
fl = 1;
dfs(v);
}
if (!fl) tr[tot].pb(u);
}
int rt[N];
int main() {
int n; read(n);
For (i, 1, n) { int x; read(x); add(i, x); }
For (i, 1, n)
if (!dfn[i]) tarjan(i);
For (u, 1, n)
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if (col[v] != col[u])
du[col[v]]++, rd[col[u]]++, addedge(col[v], col[u]);
}
int Ans = 0;
For (i, 1, color) {
if (!rd[i]) {
rt[i] = 1;
tr[++tot].pb(i);
dfs(i);
if (tr[tot].size() == 2 && tr[tot][0] == tr[tot][1]) continue;
}
}
For (i, 1, color) {
if (!du[i]) {
if (tot > 1) Ans++;
else if (!rt[i]) Ans++;
}
}
printf ("%d\n", Ans);
if (!Ans) return 0;
if (tot == 1) {
int m = tr[1].size() - 1;
For (i, 1, m) printf ("%d %d\n", node[tr[1][0]], node[tr[1][i]]);
return 0;
}
For (id, 1, tot) {
int m = tr[id].size() - 1;
For (i, 2, m) printf ("%d %d\n", node[tr[id][0]], node[tr[id][i]]);
if (id < tot)
printf ("%d %d\n", node[tr[id][0]], node[tr[id + 1][1]]);
}
printf ("%d %d\n", node[tr[tot][0]], node[tr[1][1]]);
return 0;
}
|
