Bridges: The Final Battle
Does your thesis have practical applications?
_____________________________________________________
Popular question
Legend
Sergey is nearing the completion of his thesis. Since December, the topic has remained unchanged: "Dynamic 2-Edge-Connectivity Problem". The algorithm is developed, tested, and verified with a complexity of O(K log K). Now, the only remaining task is to write the section on "practical applications".
But what practical use could there be for the "Dynamic 2-Edge-Connectivity Problem"? It's a challenging question, almost as tough as the problem itself. However, the thesis must be defended, so a solution is needed quickly.
Here's a practical application: you can create a competition problem based on this topic!
Problem
You are given an undirected graph with up to 10^5 vertices. Initially, the graph has no edges. You need to handle queries of the form ADD x y and DEL x y to add or remove an edge between vertices x and y.
At any moment, you must determine how many bridges are in the graph.
There are no multiple edges or loops at any time.
If a "delete an edge" command is issued, the edge is guaranteed to be present in the graph.
Solution to the Problem
A thesis is called a thesis because it can't be written in just 5 hours. Therefore, you are provided with a total of 5 hints:
Add an edge and remove an edge - make an edge "alive" for a certain time interval.
Use the "Divide and Conquer" method.
Compress the biconnected components.
Even when the biconnected components are already compressed, if there are few queries, the graph can still be significantly reduced.
There is a solution with O(K log K) complexity.
Input
The first line contains the integers N and K: the number of vertices and the number of queries, respectively (1 ≤ N ≤ 10^5, 1 ≤ K ≤ 10^5).
The next K lines each contain a query. Each query begins with the word "ADD" or "DEL" to add or delete an edge, respectively. Following this word are two integers a and b, which specify the edge. 1 ≤ a, b ≤ N, a ≠ b.
Output
After each query, output a single number indicating how many bridges are currently in the graph.