102294: [AtCoder]ABC229 E - Graph Destruction

Problem Statement

Given is an undirected graph with $N$ vertices and $M$ edges.
Edge $i$ connects Vertices $A_i$ and $B_i$.

We will erase Vertices $1, 2, \ldots, N$ one by one.
Here, erasing Vertex $i$ means deleting Vertex $i$ and all edges incident to Vertex $i$ from the graph.

For each $i=1, 2, \ldots, N$, how many connected components does the graph have when vertices up to Vertex $i$ are deleted?

Constraints

• $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$.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

Output

Print $N$ lines.
The $i$-th line should contain the number of connected components in the graph when vertices up to Vertex $i$ are deleted.

Sample Input 1

6 7
1 2
1 4
1 5
2 4
2 3
3 5
3 6

Sample Output 1

1
2
3
2
1
0

The figure above shows the transition of the graph.

Sample Input 2

8 7
7 8
3 4
5 6
5 7
5 8
6 7
6 8

Sample Output 2

3
2
2
1
1
1
1
0

The graph may be disconnected from the beginning.

问题描述

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

我们将按顺序删除顶点$1,2,\ldots,N$。其中，删除顶点$i$意味着从图中删除顶点$i$和所有与顶点$i$相邻的边。

对于每个$i=1,2,\ldots,N$，当删除顶点$1,2,\ldots,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$行应包含当删除顶点$1,2,\ldots,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

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