This question has two type of queries:
- Delete an edge in graph
- Update/Query some information
Had query 1 would have been insert an edge in graph, we would have Disjoint Set Union Data Structure and easily solved this question, but here it is to delete.
Solution: First of all create disjoint set union on graph after deleting all edges which are going to deleted by some query. In other words, graph should be what it would have been after processing all queries in input. Now start answering queries from last query(i.e. in reverse order). Each “delete edge” query is now changed to “insert edge” query which can be handled by dsu easily.