Save the Forest

The map actually forms a tree. The tree nodes are disconnected at the beginning. Each update operation requires you to connect two nodes. The query operation requires you to check if two nodes are in the same connected component. This two operations can be done with DSU data structure.

To execute the back operation we need to restore the the states of the DSU nodes. So, we need to save the previous states of each DSU node before changing them. Implementing or using Stack data structure will help us in that case. Whenever a Back operation occurs, we gonna keep popping out the previous states from the stack.