Hello codeforces,

I was solving this problem:

You are given a graph, and you have to answer queries of type:
1) Delete edge from U to V
2) Add edge from U to V
3) See if vertexes U and V are in the same connected component.

I couldn't come with an online solution, but I think I found an offline one.

So first I compress all queries of adding or removing and edge as: edge from U to V is available in time [i; j], where i is the time of adding and j is time of removing. Now we can do divide and conquare with dsu. This will be like that:

Rec(L, R, dsu)
{
    Look for all queries that are q.L <= L and R <= q.R
    ([L; R] lies in [q.L; q.R]) and add unite q.U and q.V in dsu

    IF L == R -> if query[L] is of type 3 then answer it and stop (and also undo changes to dsu).

    Mid = (L + R) / 2;
    Rec(L, Mid, dsu);
    Rec(Mid + 1, R, dsu);

    Undo changes to dsu
}

So this solution is O(M*logM*Cost_of_dsu). But the problem is in the DSU (the undoing of operations). I couldn't find how to do persistent DSU or DSU with restoring/undoing/backtracking. So if someone knows how to do this I will really appriciate if he helps! :)

PS: By DSU I mean disjoint set union