← 返回题目列表

Codeforces · 2073/C

C. 仙人掌连接

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Cactus Connectivity - 原题 PDF 第 1 页
原题PDF第5页
Cactus Connectivity - 原题 PDF 第 2 页
原题PDF第6页
可复制的 PDF 提取文本
Problem C
                  Cactus Connectivity
                     Time limit: 2 seconds


You are interested in the topic of graphs and their properties. In this problem, we assume that all graphs are simple
undirected graphs, meaning there is at most one edge connecting any pair of vertices and each edge connects different
vertices.

A simple cycle of a graph is a sequence of three or more distinct vertices (v1, v2, . . . , vc) such that there exists an edge
connecting vertices vi and vi+1 for each 1 ≤i < c and there also exists an edge connecting vertices v1 and vc. For
a simple cycle (v1, v2, . . . , vc), its edge set is defined as {(v1, v2), (v2, v3), . . . , (vc−1, vc), (vc, v1)}, where (vi, vj)
represents an edge connecting vertices vi and vj. Two simple cycles are the same if they share the same edge set.

A graph is a cactus if any two distinct simple cycles share at most one common vertex. For example, Figure C.1
illustrates three graphs. Graph X is a cactus since the two simple cycles (1, 2, 3) and (3, 4, 5) only share vertex 3
as the common vertex. Note that the sequence of vertices (1, 2, 3, 4, 5, 3) does not form a simple cycle since vertex
3 appears twice. Also, the simple cycle (2, 3, 1) is the same simple cycle as the simple cycle (1, 2, 3). Meanwhile,
graph Y is not a cactus since the two simple cycles (1, 2, 4) and (2, 3, 4) share vertices 2 and 4 as the common vertices.
Graph Z is a cactus since there is only one simple cycle.


         1        2        5               1        4               1        2



                  3        4               2        3                       3        4

               Graph X                      Graph Y                      Graph Z

                        Figure C.1: Graphs X and Z are cactii. Graph Y is not a cactus.

A graph is connected if there is a path connecting every pair of vertices. In particular, a graph with one vertex is
connected.

For any positive integer k, a graph is k-edge-connected if, for any set of fewer than k edges, removing those edges
leaves the graph connected.  In particular, all connected graphs are 1-edge-connected.  For example, graph Y  in
Figure C.1 is 1-edge-connected and 2-edge-connected, but not 3-edge-connected, since removing both edges incident
to vertex 1 does not leave the graph connected.

A graph H is a supergraph of a graph G if H can be obtained by adding zero or more vertices and edges to G without
removing any vertices and edges from G. Note that two graphs are the same if they have the same set of vertices and
the same set of edges. For example, in Figure C.1 above, graph X is a supergraph of graph Z, while graph Y is not a
supergraph of graph Z since it is missing the edge connecting vertices 1 and 3.

The connectivity value of a graph G is the smallest positive integer k such that, for any k-edge-connected graph H
that is a supergraph of G, removing all the edges of G from H keeps H connected. For example, in Figure C.1 above,
graph X is a 2-edge-connected supergraph of graph Z, and removing all the edges of Z from X leaves vertices 1 and
2 disconnected from the rest, as illustrated by Figure C.2 below. Therefore, the connectivity value of Z is more than
2. It can be shown that the connectivity value of Z is 3.

You are given a cactus with n vertices and m edges, where the vertices are numbered from 1 to n and the edges are 1


The 2025 ICPC Asia Pacific Championship Problem C: Cactus Connectivity

1        2        5



                                              3        4


                           Figure C.2: Removing the edges of graph Z from graph X


to m. Edge i connects vertices ui and vi. You are required to compute the connectivity value of the cactus.

Input

The first line of input contains two integers n and m (1 ≤n ≤100 000; 0 ≤m ≤200 000). The i-th of the next
m lines contains two integers ui and vi (1 ≤ui < vi ≤n). The input represents a cactus with at most one edge
connecting any pair of vertices.

Output

Output the connectivity value of the given graph.


 Sample Input #1                          Sample Output #1
 4 3                                    3
 1 2
 2 3
 1 3


Explanation for the sample input/output #1

This corresponds to graph Z from the problem description.


 Sample Input #2                          Sample Output #2
 3 0                                    1



Explanation for the sample input/output #2

Any 1-edge-connected supergraph is a connected graph. Since the given graph has no edges, removing all the edges
of the given graph from a connected graph keeps the graph connected.





The 2025 ICPC Asia Pacific Championship Problem C: Cactus Connectivity