Subtask 1

For a graph with ~N \le 3~ nodes and no self loops, it can be shown that there will always be a way to pave the roads; the answer is YES for each query.

Time Complexity: ~\mathcal O(Q)~

Subtask 2

The first observation is that determining whether the road paver can pave all the roads is equivalent to determining whether there is an Eulerian path in the graph. An Eulerian path exists if and only if there are either ~0~ or ~2~ vertices with odd degrees, and the edges of the graph are connected. We can treat a new requirement as adding ~x_i~ to the degree of vertices ~a_i~ and ~b_i~. We can determine if the edges are connected by performing a depth first search from any vertex incident to an edge after each update.

Time Complexity: ~\mathcal O(N \cdot Q)~

Subtask 3

To quickly determine whether a graph is connected, we can instead use the Union-Find data structure, allowing us to quickly query the size of a connected component. The size of the connected component of any arbitrary vertex incident to an edge is equal to the number of vertices we have encountered in the input if and only if the graph is connected. The number of odd degree vertices can be maintained in constant time after each update.

Time Complexity: ~\mathcal O(N + Q \cdot \alpha(N))~