仙人掌变树

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

给定一张特殊的无向连通图，其中每个顶点至多属于一个简单环。

你需要删除若干条边，使剩余图成为一棵树。对于每个顶点 $i$，独立地选择删边方案，并考虑所得树中顶点 $i$ 到所有叶子的距离最大值。请输出这个最大值在所有合法删边方案中的最小值。

不同顶点对应的最优删边方案可以不同。树中度数不超过 $1$ 的顶点视为叶子；当图仅含一个顶点时，该顶点也是叶子。

输入格式

第一行包含两个整数 $n,m$，分别表示顶点数和边数。

接下来 $m$ 行，每行包含两个整数 $u,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\le n\le 5\times 10^5$，$n-1\le m\le n-1+\lfloor n/3\rfloor$，$1\le u,v\le n$ 且 $u\ne v$。