题目描述

给你一个包含 $n$ 个节点 $m$ 条边的无向图。节点编号从 $1$ 到 $n$（图中不存在重边和自环，但是图不一定连通）。

然后你需要一次删除第 $1, 2, \ldots, n$ 个节点（每删除一个节点，你也要同时删除连接该节点的边）。

并且每删除一个节点后，你都需要回答出此时图中的连通块个数。

输入格式

第一行，两个整数 $n$ 和 $m$，以空格分隔（$1 \le n \le 2 \cdot 10^5$, $0 \le m \le \min( \frac{n(n-1)}{2} , 2 \cdot 10^5 )$）。

接下来 $m$ 行，每一行包含两个整数 $u_i$ 和 $v_i$，表示图中一条边连接的两个节点的编号（$1 \le u_i, v_i \le n, u_i \neq v_i$）。

输出格式

输出共 $n$ 行，每一行包含一个整数。

其中第 $i$ 行的整数表示：删除图中编号 $\le i$ 的所有点以及连接它们的边后，剩余的图中连通块的个数。

样例

6 7
1 2
1 4
1 5
2 4
2 3
3 5
3 6

1
2
3
2
1
0

8 7
7 8
3 4
5 6
5 7
5 8
6 7
6 8

3
2
2
1
1
1
1
0

说明/提示

样例 1 解释

下图中演示了依次删除后节点 $1, \ldots, 6$ 后剩余的图的情况：