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.
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).
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.
4 4 3 2 1
YES 4 1 4 2 1 3
3 3 1 2
NO
In the first sample test a permutation transforms edge (4, 1) into edge (1, 4), edge (4, 2) into edge (1, 3) and edge (1, 3) into edge (4, 2). These edges all appear in the resulting tree.
It can be shown that in the second sample test no tree satisfies the given condition.
题目大意：有n个点，编号为1~n，给出一个1~n的一个排列p，求是否能使这n个点构成一棵树，满足如果点i和点j之间有边相连，那么$p_i$和$p_j$之间也有边相连。如果存在的话输出这棵树的所有边。
因为p是n的排列，所以如果连边$i\rightarrow p_i$，会形成一张由若干个简单环组成的图（这张图和要求的树没关系）。如果有一元环，那把所有的点连到这个点上就行了。如果有二元环且没有奇环，那么把其他环上的点交替连到这两个点上就行了。否则无解。
不过我不会证明为什么没有一元环或二元环就无解，网上题解大多是口胡的，和同学讨论了半天还是不会来。。。
代码在此。
评论 (0)
