题目大意：给你一个有1-n组成的序列p，让你构造一棵树，如果节点a和b之间有一条边，则p[a]和p[b]之间也有一条边。
思路：没啥思路，看了题解菜爆。
我们可以把1-n个数分到若干个集合里边，一个集合里边的元素要满足按顺序转移改变的性质，如果有其中一个集合的元素等于数量等于1
或者其中一个集合的元素数量等于二，并且没有集合有奇数个元素。 因为我们需要用一个集合当作树的基准来构造，将其他集合的元素
连到这个基准上，所以如果这个基准的元素大于三个他们之间必然成环，并且如果其他集合有奇数个元素，那么循环一圈后肯定会产生矛盾。
还有要注意的一点是，一个集合不一定是一个圈，可能有一段出来的尾巴，那我们先从没有入度的点开始dfs就行了。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+;
int base[],p[N],vis[N],n;
bool in[N];
vector<int>ans;
bool dfs(int cur,int step)
{
vis[cur]=step;
ans.push_back(cur);
if(!vis[p[cur]]) return dfs(p[cur],step+);
int t=step+-vis[p[cur]];
return base[]==base[] || t== || t%==;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&p[i]);
in[p[i]]=;
if(i==p[i]) base[]=base[]=i;
}
if(base[]==)
{
for(int i=;i<=n;i++)
{
if(i==p[p[i]])
{
base[]=i;
base[]=p[i];
break;
}
}
}
if(base[]==) puts("NO");
else
{
vis[base[]]=vis[base[]]=;
for(int i=;i<=n;i++)
{
if(!in[i])
{
if(!dfs(i,))
{
puts("NO");
return ;
}
}
}
for(int i=;i<=n;i++)
{
if(!vis[i])
{
if(!dfs(i,))
{
puts("NO");
return ;
}
}
}
puts("YES");
if(base[]!=base[]) printf("%d %d\n",base[],base[]);
int len=ans.size();
for(int i=;i<len;i++) printf("%d %d\n",base[i&],ans[i]);
puts("");
}
}