If you naively simulate the operations of queries, we need at worst an \(\mathrm{\Theta}(QN)\) time to process all the queries, so it is hopeless to finish it in the time limit.
Instead, for acceleration, let us define a constant \(B\), and divide \(N\) vertices into “a group of vertices with degrees more than or equal to \(B\)” and “a group of vertices with degrees less than \(B\),” and treat them differently depending on the group.

We inspect the queries in the order of input. For \(i = 1, 2, \ldots, Q\), we process Query \(i\) through the following steps, Step 1 through Step 3.

Step 1: Replace the integer currently written on Vertex \(x_i\) to the correct value (described later).
Step 2: Let \(X\) be the “correct” value written on Vertex \(X\). Step 3: Depending on whether the degree of Vertex \(x_i\) is less than \(B\) or not, perform either (a) or (b) described below.

(a) If the degree of Vertex \(x_i\) is less than \(B\)

For every vertex adjacent to Vertex \(x_i\), we replace the integer written on it with \(X\). Here, we also record to each vertex that “the number has been replaced by Query \(i\).”
The time required for this process is \(O(B)\), since Vertex \(x_i\) has a degree less than \(B\).

(a) If the degree of Vertex \(x_i\) is more than or equal to \(B\)

Instead of replacing all the integers written on the vertices adjacent to Vertex \(x_i\), we place a signboard to Vertex \(x_i\) indicating that “all the integers written on the vertices adjacent to this vertex has been replaced to \(X\) by Query \(i\).” If there was already a signboard placed by a query in the past on Vertex \(x_i\), we remove the signboard and retain only the latest one.
Placing and removing a signboard can be achieved in an \(O(1)\) time, implemented as updates of variables.

Regarding with Step 1: “Replace the integer currently written on Vertex \(x_i\) to the correct value”

In the case (b) above, we do not update the vertex that has to be updated, but just place a signboard instead. Therefore, right before performing Step 1, the integer currently written on Vertex \(x_i\) may be different to the integer that actually should be written on. So, we have to check all the signboards placed at vertices adjacent to Vertex \(x_i\) with degrees more than or equal to \(B\) in order to reflect the update applied to the integer written on Vertex \(x_i\).
Since there are at most \(2M/B\) vertices with degrees more than or equal to \(B\), this step costs \(\mathrm{O}(M/B)\) time.

This way, we can process all the queries in a total of \(\mathrm{O}(Q(B+M/B))\) time. We can set the value \(B\) to about \(\sqrt{M}\), so that every query is processed in an \(\mathrm{O}(Q\sqrt{M})\) time, so that the entire problem is solved in a total of \(\mathrm{O}(Q\sqrt{M})\) time.