CF576B.Invariance of Tree

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 = _p_1_p_2... p__n, if for any two vertices of the tree u and v the condition holds: "vertices u and v are connected by an edge if and only if vertices p__u and p__v are connected by an edge".

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

大小为 $n$ 的树是一个由 $n$ 个顶点构成的无向连通图，且不含环。

考虑某个含 $n$ 个顶点的树。若对树中任意两个顶点 $u$ 和 $v$，均满足如下条件：“顶点 $u$ 与 $v$ 之间有边相连，当且仅当顶点 $p_u$ 与 $p_v$ 之间有边相连”，则称该树关于排列 $p = p_1 p_2 \dots p_n$ 是不变的（invariant）。

现给定一个大小为 $n$ 的排列 $p$。请构造一棵大小为 $n$ 的树，使其关于给定排列 $p$ 不变。

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 p__i (1 ≤ p__i ≤ n).

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 排列的长度（也等于所求树的大小）。

第二行包含一个排列 $p_i$（$1 \leq p_i \leq 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.

如果所求的树不存在，则输出 "NO"（不带引号）。

否则，输出 "YES"，然后输出 $n-1$ 行，每行包含两个整数——即你所找到的树中某条边所连接的两个顶点的编号。顶点编号从 1 开始，边的输出顺序以及每条边中两个顶点的顺序均无关紧要。

若存在多种解，输出任意一种即可。

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.

在第一个样例测试中，一个置换将边 $(4, 1)$ 变为边 $(1, 4)$，将边 $(4, 2)$ 变为边 $(1, 3)$，并将边 $(1, 3)$ 变为边 $(4, 2)$。这些边均出现在结果树中。

可以证明，在第二个样例测试中，不存在满足给定条件的树。