## Editorial for Wesley's Anger Contest 3 Problem 4 - Canadian Construction Crew

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: wleung_bvg

For a graph with 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:

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 or vertices with odd degrees, and the edges of the graph are connected. We can treat a new requirement as adding to the degree of vertices and . 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: