给你一个特殊的连通无向图,其中每个顶点最多属于一个简单循环。
您的任务是根据需要删除尽可能多的边,以将该图转换为树(无环的连通图)。
对于每个节点,独立地输出它与结果树中的叶子之间的最大距离,假设您要以最小化该距离的方式删除边缘。
输入
输入的第一行包含两个整数 $$$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$$$ 的最大距离的一种可能方法是删除下图中的标记边缘:
请注意,为了最小化不同节点的答案,您可以删除不同的边。