The problem statement is equivalent to as follows.

Given is a graph \(G\) of \(N\) vertices and \(M\) vertices, and \(N\) pieces.
Edge \(i\) connects Vertices \(a_i\) and \(b_i\), and Piece \(P_i\) is placed on Vertex \(i\).
You are allowed to swap pieces on two vertices connected by an edge.
Is it possible to make Piece \(i\) placed on Vertex \(i\) for all \(i\)?

If there exists \(i\) such that Vertex \(i\) and the vertex which Piece \(P_i\) is placed on belong to different connected components, then it is obviously impossible.

Conversely, if there is no such \(i\), then it is always possible.
This is why: if you repeat “choosing an arbitrary edge that is not a bridge and removing it,” then it ultimately becomes a forest without changing the connectivity. You can place the desired piece to each vertex in order, with leaves processed first.

The number of operations is at most \(999 + 998 + \ldots + 1 = 499500\), so the problem has been solved.

Note that in the editorial we constructed the forest by removing edges, but when implementing it is probably better to add edges using Union-Find.