← 返回题目列表

Codeforces · 576/B

B. 树的不变性

中文机器翻译题面 查看原题

大小为 n 的树是由 n 个没有环的顶点组成的无向连通图。

考虑一些有 n 个顶点的树。我们称树相对于排列 p = p1p2... pn 不变,如果对于树 u 和 v 的任意两个顶点,条件成立:“当且仅当顶点 pu 和 pv 通过边连接时,顶点 u 和 v 通过边连接”。

给定大小为 n 的排列 p。找到一些树大小 n,相对于给定的排列不变。

输入

第一行包含数字 n (1 ≤ n ≤ 105) — 排列的大小(也等于查找树的大小)。

第二行包含排列 pi (1 ≤ pi ≤ n)。

输出

如果查找的树不存在,则打印“NO”(不带引号)。

否则,打印“YES”,然后打印 n - 1 行,每行包含两个整数 - 由您找到的树的边连接的顶点数。顶点从 1 开始编号,边的顺序以及边内顶点的顺序并不重要。

如果有多个解,则输出其中任意一个。

示例

输入 #1

4
4 3 2 1

输出 #1

YES
4 1
4 2
1 3

输入 #2

3
3 1 2

输出 #2

NO

注意

在第一个示例测试中,排列将边缘 (4, 1) 转换为边缘 (1, 4),将边缘 (4, 2) 转换为边缘 (1, 3),将边缘 (1, 3) 转换为边缘 (4, 2)。这些边都出现在生成的树中。

可以证明,在第二个样本测试中没有树满足给定的条件。