Bipartite Checking
Contest: Educational Codeforces Round 22
Difficulty rating: 2500
Tags: data structures, dsu, graphs

You are given an undirected graph consisting of n vertices. Initially there are no edges in the graph. Also you are given q queries, each query either adds one undirected edge to the graph or removes it. After each query you have to check if the resulting graph is bipartite (that is, you can paint all vertices of the graph into two colors so that there is no edge connecting two vertices of the same color).

Input format:
The first line contains two integers n and q (2 ≤ n, q ≤ 100000).

Then q lines follow. ith line contains two numbers xi and yi (1 ≤ xi < yi ≤ n). These numbers describe ith query: if there is an edge between vertices xi and yi, then remove it, otherwise add it.

Output format:
Print q lines. ith line must contain YES if the graph is bipartite after ith query, and NO otherwise.

Constraints:
Time limit: 6.0 s
Memory limit: 256.0 MB

Example input:
3 5
2 3
1 3
1 2
1 2
1 2

Example output:
YES
YES
NO
YES
NO

Editorial:
If the edges were only added and not deleted, it would be a common problem that is solved with disjoint set union. All you need to do in that problem is implement a DSU which maintains not only the leader in the class of some vertex, but also the distance to this leader. Then, if we try to connect two vertices that have the same leader in DSU and the sum of distances to this leader is even, then we get a cycle with odd length, and graph is no longer bipartite.
But in this problem we need to somehow process removing edges from the graph.
In the algorithm I will describe below we will need to somehow remove the last added edge from DSU (or even some number of last added edges). How can we process that? Each time we change some variable in DSU, we can store an address of this variable and its previous value somewhere (for example, in a stack). Then to remove last added edge, we rollback these changes — we rewrite the previous values of the variables we changed by adding the last edge.
Now we can add a new edge and remove last added edge. All these operations cost (O(logn)) because we won't use path compression in DSU — path compression doesn't work in intended time if we have to rollback. Let's actually start solving the problem.
For convinience, we change all information to queries like "edge (x, y) exists from query number l till query number r". It's obvious that there are no more than q such queries. Let's use divide-and-conquer technique to make a function that answers whether the graph is bipartite or not after every query from some segment of queries [a, b]. First of all, we add to DSU all the edges that are present in the whole segment (and not added yet); then we solve it recursively for $$\left[a,\left[\frac{a+b}{2}\right]\right]$$ and $$\left[\left\lfloor\frac{a+b}{2}\right\rfloor+1,b\right]$$; then we remove edges from DSU using the rollback technique described above. When we arrive to some segment [a, a], then after adding the edges present in this segment we can answer if the graph is bipartite after query a. Remember to get rid of the edges that are already added and the edges that are not present at all in the segment when you make a recursive call. Of course, to solve the whole problem, we need to call our function from segment [1, q].
Time complexity is $${\mathcal O}(q\log^{2}q)$$, because every edge will be added only in $$O(\log q)$$ calls of the function.