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 自动生成**