Cactus to Tree
Contest: Codeforces Round 480 (Div. 2)
Difficulty rating: 2900
Tags: dp, graphs, trees

You are given a special connected undirected graph where each vertex belongs to at most one simple cycle.

Your task is to remove as many edges as needed to convert this graph into a tree (connected graph with no cycles).

For each node, independently, output the maximum distance between it and a leaf in the resulting tree, assuming you were to remove the edges in a way that minimizes this distance.

Input format:
The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 5\cdot 10^5$$$), the number of nodes and the number of edges, respectively.

Each of the following $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u,v \leq n$$$, $$$u \ne v$$$), and represents an edge connecting the two nodes $$$u$$$ and $$$v$$$. Each pair of nodes is connected by at most one edge.

It is guaranteed that the given graph is connected and each vertex belongs to at most one simple cycle.

Output format:
Print $$$n$$$ space-separated integers, the $$$i$$$-th integer represents the maximum distance between node $$$i$$$ and a leaf if the removed edges were chosen in a way that minimizes this distance.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
In the first sample, a possible way to minimize the maximum distance from vertex $$$1$$$ is by removing the marked edges in the following image:

Note that to minimize the answer for different nodes, you can remove different edges.

Example input:
9 10
7 2
9 2
1 6
3 1
4 3
4 7
7 6
9 8
5 8
5 9

Example output:
5 3 5 4 5 4 3 5 4

Example input:
4 4
1 2
2 3
3 4
4 1

Example output:
2 2 2 2

Editorial:
The following solution is implemented in 136 lines, but most of it is a simple BFS and two DFS functions for finding bridges and marking cycles, the main part of the solution is implemented in 38 lines. Please check the code after (or while?) reading if it is not clear.
Note that if we run a BFS from a node $$$u$$$, the BFS spanning tree will represent the edges that we should keep to minimize the answer for node $$$u$$$. So we actually need to find the maximum length out of all shortest paths that starts at $$$u$$$ and end at every other node.
We will first focus on finding the answer for each node on one cycle:
For each node $$$u$$$ on the cycle, we can compute $$$L[u]$$$, the length of the longest shortest path that starts at node $$$u$$$ and uses only the edges that do not belong to the cycle. This can be done using BFS in $$$O(n+m)$$$ for one cycle.
Using the computed values, we can find the final answer for all nodes on the cycle in $$$O(klogk)$$$, or $$$O(k)$$$, where $$$k$$$ is the number of nodes on the cycle.
For a node $$$u$$$, we need to find a node $$$v$$$ on the cycle such that $$$L[v] + distance(u, v)$$$ is maximized, where $$$distance(u,v)$$$ is the length of the shortest path between $$$u$$$ and $$$v$$$ on the cycle. Therefore, the answer with regards to each node $$$u$$$ will be the maximum between $$$L[u]$$$ and $$$L[v] + distance(u, v)$$$, for each node $$$v$$$ in the same cycle as $$$u$$$.
We can do this using a heap and prefix sums idea as follows: loop for $$$2k$$$ iterations over the cycle nodes, in the $$$i^{th}$$$ iteration ($$$0 \leq i < 2k$$$) add the value $$$L[cycle[i \bmod k]]+2k-i$$$ to the heap with the time it was added in ($$$time = 2k-i$$$, time is decreasing), that is, add the pair ($$$L[cycle[i \bmod k]]+2k-i, 2k-i$$$). Now at a given iteration $$$j$$$, pop from the heap all top values added at time greater than $$$2k-j+k/2$$$, as $$$distance(u,v)$$$ can't exceed $$$k/2$$$. Now assuming the top pair in the queue is ($$$x, y$$$), then $$$x-(2k-j)$$$ is a possible answer for this node.
We need to do this again in counter-clockwise. Since we will visit each node four times, keep the maximum distance $$$Z_i$$$ found for each node $$$i$$$ in the cycle and the final answer for that node will be $$$max(L_i, Z_i)$$$.
Now if we have the answer for one cycle, when we move using an edge ($$$a, b$$$) to another cycle (or node), we only need to know one value to be able to solve the next cycle, that value is the maximum between $$$Z_a$$$ and the length of the longest path that goes through bridges other than ($$$a, b$$$). This value is increased by $$$1$$$ when passed since we will move through the edge ($$$a, b$$$).
Implementation:
Marking the bridges will help in deciding if an edge will take us outside a cycle or not so we can compute $$$L_i$$$. Also removing the bridges will make it easy to find which nodes form each cycle.
We can find any BFS spanning tree and use it to find the length of the longest path that starts at a node and uses a bridge first, note that this distance goes only down as the tree is rooted at the starting node, but the values $$$L_u$$$ for every $$$u$$$ in the first cycle will be correct so we can start with them.