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