AT_jsc2023_final_b Max Degree Sum

有一个带有 $N$ 个顶点的简单连通无向图 $G$，顶点编号为 $1$ 到 $N$。图 $G$ 有 $M$ 条边，第 $i$ 条边连接了顶点 $A_i$ 和 $B_i$。 对于每个 $k=1,2,\cdots,N$，请回答以下问题。 - 任选 $G$ 的一棵生成树 $T$，请你求出在 $T$ 中编号为 $1,2,\cdots,k$ 的顶点的度数之和的最大可能值。

输入按以下格式从标准输入读入。 > $N$ $M$ > $A_1$ $B_1$ > $A_2$ $B_2$ > ⋮ > $A_M$ $B_M$

输出 $N$ 行。对于第 $i$ 行，输出当 $k=i$ 时的答案。

### 样例解释 1 考虑 $k=1$ 的情况。使用第 1、3、4 条边的生成树时，顶点 $1$ 的度数为 $3$，这是最大值。 考虑 $k=2$ 的情况。使用第 1、2、4 条边的生成树时，顶点 $1$ 和 $2$ 的度数分别为 $2,2$，它们的度数和为 $4$。不存在顶点 $1$ 和 $2$ 的度数和超过 $4$ 的生成树，因此答案为 $4$。 ### 数据范围 - $2 \leq N \leq 250000$ - $N-1 \leq M \leq 250000$ - $1 \leq A_i,B_i \leq N$ - 给定的图是简单且连通的。 - 输入的所有值都是整数。 由 ChatGPT 5 翻译