N - Tree Swapping Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 番目と Y_i 番目の要素を入れ替える。
  3. 最終的な Q を f(E) とする。

\left(1, \ldots, N \right) の順列 P と M 個の辺 (A_i, B_i) が与えられます。M 個の辺をすべて含み、木をなすような辺の列 E であって、f(E) = P を満たすものがあるかを判定し、存在する場合は一つ出力してください。複数存在する場合はどれを出力しても構いません。

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) と変化します。