小蓝的合并游戏

• 时间限制：1.0 s
• 内存限制：512.0 MB

题目描述

小蓝有 $n$ 个数字，编号 $1 \sim n$，一开始每个数字自己单独是一个「家族」。

小蓝会做 $k$ 次合并操作，每次给出两个编号 $a, b$：把 $a$ 所在的家族和 $b$ 所在的家族合并成一个家族（如果它们本来就在同一个家族里，就什么都不用做）。

每做完一次操作，小蓝都想知道：现在一共有多少个家族？请你帮帮他。

输入格式

第一行两个整数 $n, k$。

接下来 $k$ 行，每行两个整数 $a, b$，表示一次合并操作。

输出格式

共 $k$ 行，每行一个整数，表示这一次操作之后一共有多少个家族。

输入样例

4 3
1 2
3 4
2 4

输出样例

3
2
1

数据范围

• $1 \le n \le 100000$
• $1 \le k \le 200000$
• $1 \le a, b \le n$

提示

用并查集维护。用一个计数器记录当前家族数：一开始是 $n$，每当一次合并真正把两个不同家族并到一起时，计数器就减 1。如果 $a, b$ 已经在同一个家族，计数器不变。