問題文

頂点に $1$ から $N$ までの、辺に $1$ から $M$ の番号が付けられた $N$ 頂点 $M$ 辺の単純無向グラフがあります。 $i = 1, 2, \dots, M$ について $i$ 番目の辺は頂点 $u_i$ と $v_i$ を結んでいます。

時刻 $0$ において、頂点 $1$ は黒く塗られており、それ以外の頂点は白く塗られています。 また、時刻 $i = 1,2,\dots, N$ において以下のイベントが発生します。

• イベント：$1, 2, 3$ の順に操作を行う。
1. 白く塗られている頂点であって、隣接する頂点に黒く塗られている頂点が存在するものをすべて赤色に塗り替える
2. 黒く塗られている頂点をすべて白色に塗り替える
3. 赤く塗られている頂点をすべて黒色に塗り替える

$i = 1, 2, \dots, N$ について、時刻 $i$ におけるイベントが発生した直後に黒く塗られている頂点の個数を出力してください。

入力

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

制約

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le \min \left( 2 \times 10^5, \frac{N(N-1)}{2} \right)$
• $1 \le u_i < v_i \le N$
• $(u_i, v_i) \neq (u_j, v_j) \quad (i \neq j)$
• 入力は全て整数

出力

$N$ 行出力せよ。$x$ 行目には $i = x$ における答えを出力せよ。

サンプル

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

2
2
4
2
4
2

3 1
1 2

1
1
1

10 10
3 6
2 5
6 10
2 6
3 10
2 7
6 9
1 5
1 7
4 8

2
2
3
5
3
5
3
5
3
5