Есть n вершин неориентированного графа, в нем же нет ребер. В граф постепенно добавляются m ребер.
После каждого добавления ребра требуется узнать количество компонент связности.
В графе могут быть петли и кратные ребра.
Входные данные:
В первой строке два числа - n и m (1 <= n <= 300000, 0 <= m <= 500000) - количество вершин графа и количество добавляемых ребер.
В следующих m строках по два числа u, v (1 <= u, v <= n) - они значат, что в граф добавили ребро (u, v).
Выходные данные:
После каждого добавления ребра выведите количество компонент связности графа.
|
Ввод |
Вывод |
|
3 2
1 2
2 3
|
2
1 |
|
3 6
1 1
2 2
3 3
1 1
2 2
1 2
|
3
3
3
3
3
2
|
(с) Ибрахим Ахмад, 2018