← 返回题目列表

AtCoder · abc229_e

H. 图破坏

中文机器翻译题面 查看原题

分数: 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

该图可能从一开始就断开连接。