終状態 \(Q = P\) から逆順に操作を行うことで，最終的に各頂点 \(v\) について \(Q_v = v\) を成り立たせられるか？という問題に言い換えます．

まず \(M = N - 1\) の場合，すなわち全体が連結である場合を考えます． 辺 \(\{u, w\}\) に関する交換をした結果，値 \(Q_u, Q_w\) が目標頂点 \(Q_u, Q_w\) から遠ざかる方向に動いてしまうと，明らかに達成不可能です． したがって，各操作では両端点の値がそれぞれの目標頂点に近付く必要があります． 逆に，交換によって両端点の値がともに目標頂点に近付く辺に関しては，どのような順番で操作を行っても結果は変わりません．（「各辺を跨ぐべき値がちょうど \(2\) 個で，それらが逆向きであること」が Yes であるための必要条件であり，それらが両端点に揃っている状態では周囲の辺が操作不可能であることから従います．） これにより，操作可能になった辺（そこで入れ替えるべき値が両端点に揃った辺）をキューやスタックで管理して貪欲に操作をシミュレートすることで，判定と解の構築を線形時間で行うことができます．

次に \(M < N - 1\) の場合を考えます． この場合，異なる連結成分を結ぶ辺を適切に追加する必要があります． ここで，連結成分内での交換では（必要に応じて）追加辺の端点ごと交換すると見なすことで，内部での交換と外部との交換の順序を入れ替えても同じ結果が得られるため，先に異なる連結成分を結ぶ辺で交換するとして一般性を失いません．（その後，各連結成分に関して上記の問題を解けばよいです．）

異なる連結成分を結ぶ辺は，各連結成分を \(1\) 頂点に縮約したグラフで木となるように追加する必要があります． すべての連結成分について，外部から欲しい値（＝内部に値として存在しない頂点番号）が \(2\) 個以上あるとすると，すべての連結成分に \(2\) 本以上の辺を接続する必要があり，全体を木にすることは不可能です． また，外部から欲しい値が \(0\) 個である連結成分には辺を接続できないため，そのような連結成分が存在する場合も全体を木にすることは不可能です． したがって，目標を達成可能であれば，必ず外部から欲しい値がちょうど \(1\) 個であるような連結成分が存在します． そのような連結成分内の不要な値（これもちょうど \(1\) つ存在する）と，外部から欲しい値を結ぶ辺を追加して交換する，という操作を全体が \(1\) つの連結成分となるまで繰り返せばよいです．

連結成分の管理に Union-Find が必要であり，それ以外の部分はすべて線形時間で処理可能なので，全体の計算量は \(\mathrm{O}(N \cdot \alpha(N))\) となります（ \(\alpha(\cdot)\) はアッカーマン関数の逆関数）．

実装例 (C, 182 ms)