First of all, let's take a look at the 3 types of operations defined in the statement. The first operation adds and edge in the (multi)graph, the second type reverts type one operations and the third one asks whether or not two nodes are in the same connected component.
Trying to build a suitable algorithm from scratch looks tricky, so we will begin by making some observations.
Firstly, we can analyse a simpler problem, the one in which we don't have any undo operations. This would be solved using a Disjoint-set data structure. Adding an edge is equivalent to merging two disjoint sets and answering a question reduces to verifying whether or not two nodes are in the same set.
Now let's get back to the original problem. Suppose we're dealing with a small number of undo operations. In this case, it would be enough to store the entire input, and then mantain a back-up disjoint-set structure before the update. Of course, that would solve any undo operation in linear time. However, the key observation is that not all elements necessarily have to be updated (e.g. when there is just one unde operation, instead of changing just a few values, you update the whole data structure).
To enhance the performance we have to observe that a type one operation modifies O(log* N) values (on average) from the disjoint data set. This means that going one step backwards also modifies O(log* N) values. When we update we can just retain in a stack the values that we have changed. When we want to go backwards, we restore the old values mantained in the disjoint data sets. This brings our final time complexity to O(M log *N) as one operation can be done once and reversed only once, implying a constant factor of 2.
