当前没有测试数据。

E - 图的破坏

得分：$500$ 分

问题描述

给定一个具有 $N$ 个顶点和 $M$ 条边的无向图。
第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

我们将逐个消除顶点 $1, 2, \ldots, N$。
这里，消除顶点 $i$ 意味着从图中删除顶点 $i$ 以及与顶点 $i$ 相关的所有边。

对于每个 $i=1, 2, \ldots, N$，在删除顶点 $i$ 之前，图有多少个连通分量？

约束

• $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)$。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入中给出：

$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

图可能从一开始就是不连通的。