← 返回题目列表

AtCoder · utpc2021_n

N. 树交换

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

配点 : 100 点

問題文

N 顶点树边序列 E = \left(\left(X_1, Y_1\right), \ldots, \left(X_{N-1}, Y_{N-1}\right) \right) 生成的排列如下: 准备 f(E) 。 除以

  1. 順列 Q = (1, \ldots, N) 。
  2. i = 1, \ldots, N - 1 按顺序 Q 的 X_i th 和 交换第 Y_i 个元素。
  3. 决赛 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) 。 编号至