Module: Disjoint set system


Problem

5 /9


Ribs

Problem

There are n vertices in an undirected graph, but it has no edges. m edges are gradually added to the graph. 
After each addition of an edge, you need to find out the number of connected components.
A graph can have loops and multiple edges.

Input:
The first line contains two numbers  - n and m (1 <= n <= 300000, 0  <= m <= 500000) - the number of graph vertices and the number of added edges. 
The next m lines contain two numbers u, v (1 <= u, v <= n) - they mean that an edge (u, v) has been added to the graph.
Output:
After each addition of an edge, print the number of connected components of the graph.

Enter Output
3 2
1 2
2 3
2
1
36
1 1
2 2
3 3
1 1
2 2
1 2
3
3
3
3
3
2

(c) Ibrahim Ahmad, 2018