AT_utpc2021_n.Tree Swapping

给定一个包含 $N$ 个顶点的树，其边由序列 $E = \left((X_1, Y_1), \ldots, (X_{N-1}, Y_{N-1})\right)$ 表示。通过以下步骤，我们可以生成一个排列 $f(E)$：

1. 开始时，准备一个自然顺序排列 $Q = (1, 2, \ldots, N)$。
2. 按顺序对 $i = 1, 2, \ldots, N-1$，交换排列 $Q$ 的第 $X_i$ 个元素和第 $Y_i$ 个元素。
3. 经过上述所有交换后，最终的排列 $Q$ 即为 $f(E)$。

现在，给你一个长度为 $N$ 的排列 $P$ 和 $M$ 条边 $(A_i, B_i)$。你需要判断是否存在一个包含这 $M$ 条边的、可以构成一棵树的边序列 $E$，能够满足 $f(E) = P$。如果存在，请输出任意一个这样的边序列；如果不存在，则输出 No。

我们保证由 $M$ 条边组成的图不会含有自环或环路。

输入数据以以下格式给出：

$N$ $M$ $P_1$ $\ldots$ $P_N$ $A_1$ $B_1$ $\ldots$ $A_M$ $B_M$

如果没有符合条件的解，则输出一行 No。
如果有解，则首先输出一行 Yes，然后从第二行开始，逐行输出符合条件的边序列 $(A_i, B_i)$：

$A_1$ $B_1$ $\ldots$ $A_{N-1}$ $B_{N-1}$

要求输出的边必须形成一棵树。如果有多个符合条件的解，则输出任意一个即可。

• 所有输入都是整数。
• $1 \le N \le 2 \times 10^5$
• $0 \le M \le N - 1$
• $1 \le P_i \le N$
• $P$ 是 $(1, \ldots, N)$ 的一个排列。
• $1 \le A_i, B_i \le N$
• $A_i \neq B_i$
• 由 $M$ 条边组成的图不会有环和多重边。

注意事项

在样例中，排列变化示例为：$(1, 2, 3) \rightarrow (2, 1, 3) \rightarrow (2, 3, 1)$。

本翻译由 AI 自动生成