删点后的连通分量

题目描述

给定一个具有 $N$ 个顶点和 $M$ 条边的无向图。

边 $i$ 连接顶点 $A_i$ 和 $B_i$。

我们将依次删除顶点 $1, 2, \ldots, N$。

这里,删除顶点 $i$ 是指从图中删除顶点 $i$ 以及所有与顶点 $i$ 相连的边。

对于每个 $i=1, 2, \ldots, N$,当删除到顶点 $i$ 为止的顶点时,图有多少个连通分量?

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

输出格式

输出 $N$ 行。

第 $i$ 行输出当删除到顶点 $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 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq \min(\frac{N(N-1)}{2} , 2 \times 10^5 )$
• $1 \leq A_i \lt B_i \leq N$
• 若 $i \neq j$,则 $(A_i,B_i) \neq (A_j,B_j)$
• 输入中的所有值均为整数