合并后的块数

难度：T2

【知识点：并查集】

前置知识：本单元此前讲解的状态、边界与实现。

题目描述

开始时有 $n$ 个顶点，编号为 $1$ 到 $n$，没有任何边，每个顶点独自构成一个连通块。

输入格式

其中 $n$ 为顶点数，顶点编号为 $1$ 到 $n$。无向边的两个端点可互相通行。

输入$n$、$m$及依次加入的$m$条无向边。允许自环和重复边。

输出格式

每加入一条边输出全图当前连通块数。

数据范围

$1\le n\le 100000$，$1\le m\le 200000$，端点在$1$..$n$。

样例输入

1 1
1 1

样例输出

1

样例输入 2

4 4
1 2
2 3
1 3
4 4

样例输出 2

3
2
2
2

样例说明 2

前两条边各减少一个连通块，后两条边不再连接不同的块。