問題文

1 から N までの番号のついた N 頂点からなる単純連結無向グラフ G があります． G は M 本の辺を持ち，i 番目の辺は頂点 A_i,B_i を結んでいます．

各 k=1,2,\cdots,N について，以下の問題に答えて下さい．

• G の全域木 T を 1 つ自由にとることを考える． このとき，T における頂点 1,2,\cdots,k の次数の総和としてあり得る最大値を求めよ．

制約

• 2 \leq N \leq 250000
• N-1 \leq M \leq 250000
• 1 \leq A_i,B_i \leq N
• 与えられるグラフは単純かつ連結．
• 入力される値はすべて整数．

入力例 1

4 4
1 2
2 3
3 1
1 4

出力例 1

3
4
5
6

k=1 について考えます． 1,3,4 番目の辺を使う全域木を考えると頂点 1 の次数が 3 になり，これが最大です．

k=2 について考えます． 1,2,4 番目の辺を使う全域木を考えると頂点 1,2 の次数がそれぞれ 2,2 になり，その和は 4 です． 頂点 1,2 の次数の和が 4 を超える全域木は存在しないため，答えは 4 です．

入力例 2

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

出力例 2

2
4
5
7
8

入力例 3

2 1
2 1

出力例 3

1
2

入力例 4

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

出力例 4

3
8
10
12
13
14
15
16
17
18