CF576B Invariance of Tree

一棵大小为 $n$ 的树是一个包含 $n$ 个顶点、没有环的无向连通图。 考虑一棵有 $n$ 个顶点的树。若对于排列 $p=p_1 p_2\ldots p_n$，对于树上任意两个顶点 $u$ 和 $v$，都满足：“当且仅当顶点 $u$ 和 $v$ 之间有边时，顶点 $p_u$ 和 $p_v$ 之间也有边”，则称这棵树对于该排列是“不变的”。 给定一个长度为 $n$ 的排列 $p$。请你找出一棵大小为 $n$ 的，对于该排列 $p$ 不变的树。

第一行包含一个整数 $n$（$1 \leq n \leq 10^{5}$），表示排列的大小（也等于待求树的顶点数）。 第二行包含 $n$ 个整数 $p_i$（$1 \leq p_i \leq n$），表示排列 $p$。

若不存在满足要求的树，输出 “NO”。 否则，输出 “YES”，并在接下来的 $n-1$ 行中，每行输出两个正整数，表示一条树中的边，两个整数为被该边连接的两个顶点的编号。顶点编号从 $1$ 开始，输出的边和边中两个顶点的顺序均不限。 如有多组解，输出任意一组均可。

在第一个样例中，排列会将边 $(4, 1)$ 映射为边 $(1, 4)$，将 $(4, 2)$ 映射为 $(1, 3)$，将 $(1, 3)$ 映射为 $(4, 2)$。这些边在结果树中都存在。 可以证明，在第二个样例中，没有任何树能满足题意。 由 ChatGPT 5 翻译