← 返回题目列表

Codeforces · 980/F

F. 仙人掌到树

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

给你一个特殊的连通无向图,其中每个顶点最多属于一个简单循环。

您的任务是根据需要删除尽可能多的边,以将该图转换为树(无环的连通图)。

对于每个节点,独立地输出它与结果树中的叶子之间的最大距离,假设您要以最小化该距离的方式删除边缘。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \leq 5\cdot 10^5$$$),分别为节点数和边数。

以下 $$$m$$$ 行中的每一行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u,v \leq n$$$, $$$u \ne v$$$),并表示连接两个节点 $$$u$$$ 和 $$$v$$$ 的边。每对节点最多由一条边连接。

保证给定的图是连通的,并且每个顶点最多属于一个简单循环。

输出

打印 $$$n$$$ 以空格分隔的整数,第 $$$i$$$ 整数表示节点 $$$i$$$ 和叶子之间的最大距离(如果以最小化此距离的方式选择删除的边)。

示例

输入 #1

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

输出 #1

5 3 5 4 5 4 3 5 4

输入 #2

4 4
1 2
2 3
3 4
4 1

输出 #2

2 2 2 2

注意

在第一个示例中,最小化距顶点 $$$1$$$ 的最大距离的一种可能方法是删除下图中的标记边缘:

请注意,为了最小化不同节点的答案,您可以删除不同的边。