分数: 500 点
问题陈述
给定一个无向图 N 顶点和 M 边缘。
边缘 i 连接顶点 A_i 和 B_i.
我们将删除顶点 1, 2, \ldots, N 一一。
在这里,擦除顶点 i 表示删除顶点 i 以及所有与顶点相关的边
图中的 i 。
对于每个 i=1, 2, \ldots, N,当顶点达到 Vertex 时,图有多少个连通分量 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
- (A_i,B_i) \neq (A_j,B_j) if i \neq j.
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
输出
打印 N 行。
的
树的 i- 第行应包含当顶点达到 Vertex 时图中连通分量的数量 i 已删除。
示例输入 1
6 7 1 2 1 4 1 5 2 4 2 3 3 5 3 6
示例输出 1
1 2 3 2 1 0

上图显示了图形的转变。
示例输入 2
8 7 7 8 3 4 5 6 5 7 5 8 6 7 6 8
示例输出 2
3 2 2 1 1 1 1 0
该图可能从一开始就断开连接。