34604번 - Cactus Connectivity 다국어

문제

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 $(v_1, v_2, \dots , v_c)$ such that there exists an edge connecting vertices $v_i$ and $v_{i+1}$ for each 1ドル ≤ i < c$ and there also exists an edge connecting vertices $v_1$ and $v_c$. For a simple cycle $(v_1, v_2, \dots , v_c),ドル its edge set is defined as $\{(v_1, v_2),(v_2, v_3), \dots ,(v_{c−1}, v_c),(v_c, v_1)\},ドル where $(v_i , v_j )$ represents an edge connecting vertices $v_i$ and $v_j$. 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.

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ドル$.

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

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ドル$ to $m$. Edge $i$ connects vertices $u_i$ and $v_i$. You are required to compute the connectivity value of the cactus.

입력

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 $u_i$ and $v_i$ (1ドル ≤ u_i < v_i ≤ n$). The input represents a cactus with at most one edge connecting any pair of vertices.

출력

Output the connectivity value of the given graph.

제한

노트