AT_utpc2021_n Tree Swapping

[problemUrl]: https://atcoder.jp/contests/utpc2021/tasks/utpc2021_n $ 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 $ 個の辺からなるグラフは自己ループや閉路を持たないことが保証されます。

入力は以下の形式で標準入力から与えられる。 > $ 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\ \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) $ からなるグラフは閉路や多重辺をもたない ### Sample Explanation 1 数列は $ (1,\ 2,\ 3)\ \rightarrow\ (2,\ 1,\ 3)\ \rightarrow\ (2,\ 3,\ 1) $ と変化します。