问题描述

给定一个无向图，包含$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$时图中剩余的连通分量数量。

样例输入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

图最初可能就是不连通的。