配点 : 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