Compute distance of each node to a cycle

Problem

You are given an undirected graph with n nodes labeled 0..n-1 and a list of edges. The graph is connected and contains exactly one simple cycle (i.e., it is a unicyclic graph).

For each node i, return dist[i] = the minimum number of edges from node i to any node on the cycle.

• Nodes that are on the cycle have distance 0 .

Example (illustrative)

If nodes {2,3,4} form the only cycle, then dist[2]=dist[3]=dist[4]=0, and nodes in trees attached to the cycle have distance equal to their shortest path length to any of {2,3,4}.

Input / Output

• Input:
  • integer n
  • edges: list of pairs (u, v)
• Output: integer array dist of length n

Constraints (assume)

• 2 ≤ n ≤ 2 * 10^5
• edges.length = n (connected unicyclic graph)
• 0 ≤ u, v < n , u != v

Notes

A linear-time approach is expected. (A common approach involves pruning leaves to identify cycle nodes, then multi-source BFS from the cycle.)