問題を次のように言い換えます。

\(N\) 頂点 \(M\) 辺のグラフ \(G\) と、\(N\) 個の駒が与えられる。
辺 \(i\) は頂点 \(a_i\) と \(b_i\) を結んでおり、頂点 \(i\) には駒 \(P_i\) が置かれている。
可能な操作は辺で結ばれた頂点同士の駒を入れ替えることである。
全ての \(i\) について、頂点 \(i\) に駒 \(i\) が置かれているようにすることはできるか？

頂点 \(i\) と、駒 \(P_i\) が置かれている頂点 が異なる連結成分に属するような \(i\) が存在するとき、明らかに不可能です。

逆にそうでないとき必ず可能です。
なぜなら、「 \(G\) の橋でない辺を任意に \(1\) つ選んで削除する」ことを繰り返すと最終的に \(G\) は連結性を保ったまま森になるので、この森において葉から順番に目標の駒を置いていけば良いからです。

操作回数は最大でも \(999 + 998 + \ldots + 1 = 499500\) 回なので、以上でこの問題を解くことができました。

なお解説では森の構築は辺の削除で行いましたが、実装上は Union-Find を用いて辺を追加していく方針がいいと思います。