题目描述

给定一个具有 $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 < 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

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