401878: GYM100551 D Bridges: The Final Battle

D. Bridges: The Final Battletime limit per test2 secondsmemory limit per test256 megabytesinputbridges3.inoutputbridges3.outDoes your research work have any practical applications? Frequently asked question

Serezha has almost finished his thesis. The subject hasn't changed since December: "Dynamic 2-Edge-Connectivity Problem". The algorithm has been invented and tested, the bound of has been proved. The only thing left is to write about "practical applications".

Well, does the problem "Dynamic 2-Edge-Connectivity Problem" indeed have any practical applications? That's not a simple question. Probably, it's even harder than the problem itself. Whatever, the thesis has to be done.

So, the first practical application: let us create a contest problem about it!

Given an undirected graph with no more than 10⁵ vertices. Initially it does not contain any edges. You have to process requests ADD x y and DEL x y — to add and to remove edge from x to y, respectively.

After each request, you should find the number of bridges in the graph.

There are no multiedges and loops.

For every request to remove an edge, the corresponding edge exists.

The thesis has to be pretty hard to be written in five hours. So you are given five hints.

1. Requests to add or remove edge make the edge "alive" during some intervals of time.
2. Use "Divide and conquer" idea.
3. Compress components of biconnectivity.
4. Even having compressed biconnectivity components, the graph can be reduced provided there are few requests.
5. The solution in exists.

Input

The first line of input contains two integers N and K: the number of vertices and requests, respectively. 1 ≤ N ≤ 10⁵, 1 ≤ K ≤ 10⁵.

The following K lines contain requests, one per line. Each request starts with a word "ADD" or "DEL", depending on the type of the request. Two integers a_i and b_i follow, describing the edge to add or to remove. 1 ≤ a_i, b_i ≤ N, a_i ≠ b_i.

Output

Write K integers: the number of bridges in the graph after each request.

ExamplesInput

4 8
ADD 1 2
ADD 2 3
ADD 1 3
DEL 2 3
DEL 1 2
ADD 2 4
ADD 1 4
ADD 2 3

Output

1
2
0
2
1
2
3
0