E - Graph Destruction Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

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

はじめからグラフが非連結なこともあります。

Score : 500 points

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.