← 返回题目列表

AtCoder · jsc2023_final_b

B. 最大度数和

中文机器翻译题面 查看原题

配点 : 600 点

問題文

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
  • 给定的图很简单且连通。
  • 所有输入值都是整数。 输出

入力

输入是按以下格式从标准输入给出的。

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

N 行。 打印 i 行中,k=i 的答案。 考虑


入力例 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