配点 : 100 点
問題文
N 顶点树边序列 E = \left(\left(X_1, Y_1\right), \ldots, \left(X_{N-1}, Y_{N-1}\right) \right) 生成的排列如下: 准备 f(E) 。 除以
- 順列 Q = (1, \ldots, N) 。
- i = 1, \ldots, N - 1 按顺序 Q 的 X_i th 和 交换第 Y_i 个元素。
- 决赛 Q 在 f(E) 。
\left(1, \ldots, N \right) 的排列 在 P 和 M 边缘 形成树的边序列,包括所有 (A_i, B_i) 。M 边。 E 和 判断是否有满足f(E) = P 的东西,如果存在则输出1。如果有多个,则输出哪一个并不重要。
M 边的图保证没有自环或循环。 由
制約
- 所有输入均为整数
- 1 \le N \le 2 \times 10^5
- 0 \le M \le N - 1
- 1 \le P_i \le N
- P 是 \left(1, \ldots, N \right) 的排列 在
- 1 \le A_i, B_i \le N
- A_i \neq B_i
- (A_i, B_i) 组成的图没有环或多重边。
入力
输入是按以下格式从标准输入给出的。
N M P_1 \ldots P_N A_1 B_1 \vdots A_M B_M
出力
如果不存在解,则写 No 。
如果存在,则在第一行
输出 Yes 后,从第二行开始,
按以下格式输出第 (A_i, B_i) 在 i 面。
A_1 B_1
\vdots
A_{N-1} B_{N-1}
但是, 表示(A_1, B_1), \ldots, (A_{N-1}, B_{N-1}) 必须形成一棵树,如果有多个答案,则输出哪一个并不重要。
入力例 1
3 1 2 3 1 3 2
出力例 1
Yes 1 2 2 3
序列是 它更改为 (1, 2, 3) \rightarrow (2, 1, 3) \rightarrow (2, 3, 1) 。 编号至