{"problem":{"name":"F. Cactus to Tree","description":{"content":"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 g","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF980F"},"statements":[{"statement_type":"Markdown","content":"You are given a special connected undirected graph where each vertex belongs to at most one simple cycle.\n\nYour task is to remove as many edges as needed to convert this graph into a tree (connected graph with no cycles).\n\nFor 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.\n\n## Input\n\nThe 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.\n\nEach 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.\n\nIt is guaranteed that the given graph is connected and each vertex belongs to at most one simple cycle.\n\n## Output\n\nPrint $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.\n\n[samples]\n\n## Note\n\nIn the first sample, a possible way to minimize the maximum distance from vertex $1$ is by removing the marked edges in the following image:\n\n<center>![image](https://espresso.codeforces.com/3fd1475a11f88f5d5fc146e80872dd0b7461024d.png)</center>Note that to minimize the answer for different nodes, you can remove different edges.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你被给定一个特殊的连通无向图，其中每个顶点至多属于一个简单环。\n\n你的任务是移除尽可能多的边，将该图转换为一棵树（无环的连通图）。\n\n对于每个节点，独立地输出在结果树中，它到某个叶子节点的最大距离，假设你以最小化该距离的方式移除边。\n\n输入的第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n lt.eq 5 dot.op 10^5$)，分别表示节点数和边数。\n\n接下来的 $m$ 行每行包含两个整数 $u$ 和 $v$ ($1 lt.eq u, v lt.eq n$, $u != v$)，表示连接节点 $u$ 和 $v$ 的一条边。每对节点之间至多有一条边。\n\n保证给定图是连通的，且每个顶点至多属于一个简单环。\n\n请输出 $n$ 个用空格分隔的整数，第 $i$ 个整数表示：若以最小化该距离的方式移除边，则节点 $i$ 到某个叶子节点的最大距离。 \n\n在第一个样例中，一种最小化顶点 $1$ 的最大距离的方法是移除下图中标记的边：\n\n注意，为了最小化不同节点的答案，你可以移除不同的边。\n\n## Input\n\n输入的第一行包含两个整数 $n$ 和 $m$ ($1 lt.eq n lt.eq 5 dot.op 10^5$)，分别表示节点数和边数。接下来的 $m$ 行每行包含两个整数 $u$ 和 $v$ ($1 lt.eq u, v lt.eq n$, $u != v$)，表示连接节点 $u$ 和 $v$ 的一条边。每对节点之间至多有一条边。保证给定图是连通的，且每个顶点至多属于一个简单环。\n\n## Output\n\n请输出 $n$ 个用空格分隔的整数，第 $i$ 个整数表示：若以最小化该距离的方式移除边，则节点 $i$ 到某个叶子节点的最大距离。\n\n[samples]\n\n## Note\n\n在第一个样例中，一种最小化顶点 $1$ 的最大距离的方法是移除下图中标记的边：注意，为了最小化不同节点的答案，你可以移除不同的边。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ G = (V, E) $ be a connected undirected graph with $ |V| = n $, $ |E| = m $, such that each vertex belongs to at most one simple cycle. Such a graph is a *cactus graph*.\n\nLet $ \\mathcal{C} $ be the set of all simple cycles in $ G $. For each cycle $ C \\in \\mathcal{C} $, let $ |C| $ denote its length (number of vertices).\n\n**Constraints**  \n1. $ 1 \\le n \\le 5 \\cdot 10^5 $  \n2. $ n - 1 \\le m \\le n + \\lfloor n/3 \\rfloor $ (since each edge is in at most one cycle, and the graph is connected)  \n3. $ G $ is connected and each vertex is in at most one cycle.  \n\n**Objective**  \nFor each vertex $ v \\in V $, define $ d^*(v) $ as the minimum possible value of the maximum distance from $ v $ to any leaf in a spanning tree $ T $ of $ G $, where $ T $ is obtained by removing exactly $ m - (n - 1) $ edges — one from each cycle, to break all cycles.\n\nCompute $ d^*(v) $ for all $ v \\in V $.\n\n**Key Insight**  \nSince $ G $ is a cactus, removing one edge from each cycle yields a spanning tree. For each cycle $ C $, the optimal edge to remove is the one that minimizes the maximum distance from any vertex to a leaf in the resulting tree.\n\nThe problem reduces to:  \nFor each vertex $ v $, compute the minimum, over all valid spanning trees $ T $ of $ G $, of the radius of $ T $ rooted at $ v $, i.e.,  \n$$\nd^*(v) = \\min_{T \\in \\mathcal{T}} \\max_{u \\in \\text{Leaves}(T)} \\text{dist}_T(v, u)\n$$  \nwhere $ \\mathcal{T} $ is the set of all spanning trees of $ G $ obtained by removing one edge per cycle.\n\n**Equivalent Reformulation**  \nFor each cycle $ C $, the optimal removal strategy for minimizing eccentricities is to remove an edge such that the resulting tree has the cycle collapsed into a path with minimal diameter contribution. The key is to compute, for each vertex, its eccentricity in the tree formed by optimally breaking cycles — which corresponds to replacing each cycle $ C $ with a path of length $ |C| - 1 $, connecting the same vertices, and choosing the “best” chord to remove to minimize maximum leaf distances.\n\nThus, for each vertex $ v $, $ d^*(v) $ equals the maximum distance from $ v $ to any leaf in the *tree* obtained by replacing each cycle $ C $ with a shortest path between its two most distant vertices (i.e., breaking the cycle at the edge opposite the farthest point from $ v $).\n\nThis leads to the following algorithmic structure:\n\nLet $ T $ be the tree obtained from $ G $ by contracting each cycle $ C $ into a single “super-node” with radius equal to $ \\lfloor |C|/2 \\rfloor $, and connecting the articulation points appropriately. Then, for each vertex $ v $, compute its eccentricity in this tree, where distances along cycles are minimized by taking the shorter arc.\n\nThus, formally:\n\nLet $ T_G $ be the *block-cut tree* of $ G $, where each cycle is represented as a block, and articulation points connect blocks. For each cycle $ C $, define its *radius* as $ r_C = \\lfloor |C|/2 \\rfloor $. For any vertex $ v \\in C $, define its *distance to the center* of $ C $ as $ \\min_{u \\in C} \\text{dist}_C(v, u) $, which is at most $ r_C $.\n\nThen, for each vertex $ v \\in V $,  \n$$\nd^*(v) = \\max_{u \\in \\text{Leaves}(T_G)} \\left( \\text{dist}_{T_G}(v, u) + \\text{rad}_u \\right)\n$$  \nwhere $ \\text{rad}_u $ is the radius contribution of the cycle containing $ u $ if $ u $ lies on a cycle, or 0 otherwise.\n\nBut since leaves of the resulting tree must be original vertices of degree 1 in the spanning tree, and the optimal edge removal in each cycle ensures that the farthest point from $ v $ within a cycle is at most $ r_C $ away, we can compute:\n\nLet $ d_{\\text{tree}}(v, u) $ be the distance between $ v $ and $ u $ in the tree formed by replacing each cycle $ C $ with a path of length $ |C| - 1 $, and let $ r_C(v) $ be the maximum distance from $ v $ to any vertex in $ C $ under optimal edge removal (i.e., $ \\max_{w \\in C} \\min(\\text{dist}_C(v,w), |C| - \\text{dist}_C(v,w)) $).\n\nActually, simpler:\n\n**Final Formal Statement**\n\nLet $ G = (V, E) $ be a cactus graph. For each cycle $ C \\in \\mathcal{C} $, define its *center* as the vertex (or pair of vertices) minimizing the maximum distance to any vertex in $ C $. The radius of $ C $ is $ r_C = \\left\\lfloor \\frac{|C|}{2} \\right\\rfloor $.\n\nFor each vertex $ v \\in V $, let $ f(v) $ be the maximum distance from $ v $ to any leaf in a spanning tree of $ G $ obtained by removing one edge per cycle to minimize this maximum.\n\nThen:  \n$$\nd^*(v) = \\max_{u \\in L} \\left( \\text{dist}_{T}(v, u) \\right)\n$$  \nwhere $ T $ is the spanning tree of $ G $ obtained by, for each cycle $ C $, removing the edge that maximizes the minimum distance from $ v $ to the farthest point in $ C $, and $ L $ is the set of leaves in $ T $.\n\nBut to compute $ d^*(v) $ efficiently:\n\nDefine the *eccentricity* of $ v $ in the cactus as the maximum distance from $ v $ to any leaf in the *tree* obtained by replacing each cycle $ C $ with a path of length $ |C| - 1 $, and computing distances via shortest paths along the cactus structure, where within each cycle, the distance between two vertices is the minimum of the two arc lengths.\n\nThen $ d^*(v) $ is the **eccentricity** of $ v $ in this metric.\n\nThus, the problem reduces to:  \nCompute the eccentricity of each vertex in the cactus graph under the shortest-path metric, where the graph is treated as a tree of cycles (i.e., the *metric closure* of the cactus).\n\nLet $ d_G(u, v) $ be the shortest-path distance in $ G $, where within each cycle, distances are computed along the shorter arc.\n\nThen:  \n$$\nd^*(v) = \\max_{u \\in V} \\left\\{ d_G(v, u) \\mid \\deg_T(u) = 1 \\text{ in some optimal spanning tree } T \\right\\}\n$$\n\nBut since in any optimal spanning tree, leaves are vertices that are not articulation points or are endpoints of pendant edges, and since removing edges from cycles doesn't create new leaves unless the cycle had degree-2 vertices, the set of possible leaves is exactly the set of vertices with degree 1 in $ G $, plus vertices on cycles that become leaves after edge removal.\n\nActually, a better characterization:\n\nIn the optimal tree, a vertex $ u $ is a leaf if and only if in $ G $, it has degree 1, or it is on a cycle and the two edges incident to it in the cycle are such that one is removed and the other is preserved, and it has no other neighbors.\n\nBut this is complex.\n\n**Simpler Final Formalization**\n\nGiven a cactus graph $ G $, define for each vertex $ v \\in V $:\n\n$$\nd^*(v) = \\max_{u \\in V} \\min_{P \\in \\mathcal{P}_{v,u}} \\text{length}(P)\n$$  \nwhere $ \\mathcal{P}_{v,u} $ is the set of paths from $ v $ to $ u $ in $ G $, and the length of a path is the number of edges, with the understanding that within each cycle, the shortest arc is taken.\n\nBut that’s just the eccentricity in the shortest-path metric of the cactus.\n\nAnd since the optimal spanning tree preserves all shortest paths (by removing the longest arc in each cycle), the maximum distance from $ v $ to any leaf in the optimal tree equals the maximum distance from $ v $ to any leaf in the cactus under the shortest-path metric.\n\nThus:\n\n**Objective**  \nFor each vertex $ v \\in V $, compute the eccentricity of $ v $ in the cactus graph $ G $, where the distance between two vertices is the length of the shortest path between them (with distances within cycles computed along the shorter arc), and the eccentricity is defined as:  \n$$\nd^*(v) = \\max_{u \\in L} d_G(v, u)\n$$  \nwhere $ L \\subseteq V $ is the set of all vertices that can be leaves in *some* spanning tree of $ G $ obtained by removing one edge per cycle.\n\nBut since every vertex that is not an articulation point of degree 2 on a cycle can be made a leaf, and articulation points cannot be leaves, the set $ L $ is exactly the set of vertices that are not cut vertices, or are leaves in the block-cut tree.\n\nActually, in a cactus, a vertex is a leaf in some spanning tree iff it is not a cut vertex that lies on more than one cycle — but each vertex is in at most one cycle.\n\nSo:  \nA vertex $ u $ is a leaf in some spanning tree iff it has degree 1 in $ G $, or it is on a cycle and has degree 2 in $ G $ (so it can become a leaf by removing one of the two cycle edges).\n\nThus, the set of possible leaves is:  \n$$\nL = \\{ u \\in V \\mid \\deg_G(u) = 1 \\} \\cup \\{ u \\in V \\mid u \\text{ lies on a cycle and } \\deg_G(u) = 2 \\}\n$$\n\nThen:  \n$$\n\\boxed{d^*(v) = \\max_{u \\in L} d_G(v, u)}\n$$  \nwhere $ d_G(v, u) $ is the shortest-path distance in $ G $, with distances within cycles computed along the shorter arc.\n\nThis is the formal statement.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF980F","tags":["dp","graphs","trees"],"sample_group":[["9 10\n7 2\n9 2\n1 6\n3 1\n4 3\n4 7\n7 6\n9 8\n5 8\n5 9","5 3 5 4 5 4 3 5 4"],["4 4\n1 2\n2 3\n3 4\n4 1","2 2 2 2"]],"created_at":"2026-03-03 11:00:39"}}