Codeforces Round #319 (Div. 1) B. Invariance of Tree 构造

B. Invariance of Tree

Time Limit: 1 Sec  

Memory Limit: 256 MB

题目连接

http://codeforces.com/contest/576/problem/B

Description

A tree of size n is an undirected connected graph consisting of n vertices without cycles.

Consider some tree with n vertices. We call a tree invariant relative to permutation p = p1p2... pn, if for any two vertices of the tree u andv the condition holds: "vertices u and v are connected by an edge if and only if vertices pu and pv are connected by an edge".

You are given permutation p of size n. Find some tree size n, invariant relative to the given permutation.

Input

The first line contains number n (1 ≤ n ≤ 105) — the size of the permutation (also equal to the size of the sought tree).

The second line contains permutation pi (1 ≤ pi ≤ n).

Output

If the sought tree does not exist, print "NO" (without the quotes).

Otherwise, print "YES", and then print n - 1 lines, each of which contains two integers — the numbers of vertices connected by an edge of the tree you found. The vertices are numbered from 1, the order of the edges and the order of the vertices within the edges does not matter.

If there are multiple solutions, output any of them.

Sample Input

4
4 3 2 1

Sample Output

YES
4 1
4 2
1 3

HINT

题意

给你一些点，以及p[i]，表示如果你i和j相连的话，那么p[i]和p[j]也必须相连

然后问你能不能构成一棵树~

如果能的话，请输出这棵树的样子

题解：

如果有i=p[i]的话，那么直接让其他所有点都连接这个点就好了

如果不存在二元环的话，那就直接输出NO，因为你随便连接一个环内的边，就会使得整个环都连边，就会错误

如果存在二元环，如果存在奇元环，那就直接输出NO，否则就让偶元环依次连过去就好了

大概第三类讨论画画图就能很轻松的证明了

代码：

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <bitset>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 1000500
#define mod 1001
#define eps 1e-9
#define pi 3.1415926
int Num;
//const int inf=0x7fffffff;
const ll inf=999999999;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//*************************************************************************************

int p[maxn];
int vis[maxn];
int deal(int x,int c)
{
    if(vis[x])
        return c;
    vis[x]=1;
    deal(p[x],c+1);
}
void solve(int x,int c,int a,int b)
{
    if(vis[x])return;
    vis[x]=1;
    if(c%2==1)
        printf("%d %d
",x,a);
    else
        printf("%d %d
",x,b);
    solve(p[x],c+1,a,b);
}
int main()
{
    int n=read();
    int flag = 0;
    for(int i=1;i<=n;i++)
    {
        p[i]=read();
        if(p[i]==i)flag=i;
    }
    if(flag)
    {
        printf("YES
");
        for(int i=1;i<=n;i++)if(flag!=i)printf("%d %d
",i,flag);
        return 0;
    }
    int flag1=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            int tmp = deal(i,0);
            if(tmp==2)flag1=i;
            if(tmp%2==1){printf("NO
");return 0;}
        }
    }
    if(!flag1){printf("NO
");return 0;}
    printf("YES
");
    memset(vis,0,sizeof(vis));
    vis[p[flag1]]=1;
    for(int i=1;i<=n;i++)
        if(!vis[i])
            solve(i,0,flag1,p[flag1]);
    return 0;
}