题目描述

你对图及其性质这一主题感兴趣。在本问题中，我们假设所有图都是简单无向图，这意味着任意一对顶点之间至多有一条边，且每条边连接不同的顶点。

一个图的简单环是一个由三个或更多不同顶点组成的序列 $(v_1, v_2, \ldots, v_c)$，使得对于每个 $1\le i<c$ 都存在一条连接顶点 $v_i$ 和 $v_{i+1}$ 的边，并且也存在一条连接顶点 $v_1$ 和 $v_c$ 的边。对于一个简单环 $(v_1, v_2, \ldots, v_c)$，其边集定义为 $\{(v_1, v_2), (v_2, v_3), \ldots, (v_{c-1}, v_c), (v_c, v_1)\}$，其中 $(v_i, v_j)$ 表示连接顶点 $v_i$ 和 $v_j$ 的边。如果两个简单环拥有相同的边集，则它们是相同的。

如果一个图中任意两个不同的简单环至多共享一个公共顶点，则该图是一个仙人掌图。例如，图 C.1 展示了三个图。图 $X$ 是一个仙人掌图，因为两个简单环 $(1, 2, 3)$ 和 $(3, 4, 5)$ 只共享顶点 $3$ 作为公共顶点。注意，顶点序列 $(1, 2, 3, 4, 5, 3)$ 不构成简单环，因为顶点 $3$ 出现了两次。此外，简单环 $(2, 3, 1)$ 与简单环 $(1, 2, 3)$ 是相同的简单环。而图 $Y$ 不是仙人掌图，因为两个简单环 $(1, 2, 4)$ 和 $(2, 3, 4)$ 共享顶点 $2$ 和 $4$ 作为公共顶点。图 $Z$ 是一个仙人掌图，因为它只有一个简单环。

:::align{center}

图 C.1：图 $X$ 和图 $Z$ 是仙人掌图。图 $Y$ 不是仙人掌图。 :::

如果任意一对顶点之间都存在一条路径，则该图是连通的。特别地，只有一个顶点的图是连通的。

对于任意正整数 $k$，如果一个图去掉任意少于 $k$ 条边后仍然连通，则该图是 $k$ 边连通的。特别地，所有连通图都是 $1$ 边连通的。例如，图 C.1 中的图 $Y$ 是 $1$ 边连通和 $2$ 边连通的，但不是 $3$ 边连通的，因为去掉与顶点 $1$ 关联的两条边后，图不再连通。

如果一个图 $H$ 可以通过向图 $G$ 添加零个或多个顶点和边而得到，且不删除 $G$ 的任何顶点和边，则 $H$ 是 $G$ 的一个超图。注意，如果两个图具有相同的顶点集和相同的边集，则它们是相同的。例如，在图 C.1 中，图 $X$ 是图 $Z$ 的一个超图，而图 $Y$ 不是图 $Z$ 的超图，因为它缺少连接顶点 $1$ 和 $3$ 的边。

图 $G$ 的连通性值是最小的正整数 $k$，使得对于任意一个 $k$ 边连通且是 $G$ 的超图的图 $H$，从 $H$ 中移除 $G$ 的所有边后，$H$ 仍然连通。例如，在图 C.1 中，图 $X$ 是图 $Z$ 的一个 $2$ 边连通超图，而从 $X$ 中移除 $Z$ 的所有边后，顶点 $1$ 和 $2$ 与其余部分不连通，如下图 C.2 所示。因此，$Z$ 的连通性值大于 $2$。可以证明 $Z$ 的连通性值为 $3$。

:::align{center}

图 C.2：从图 $X$ 中移除图 $Z$ 的边 :::

给定一个具有 $n$ 个顶点和 $m$ 条边的仙人掌图，顶点编号为 $1$ 到 $n$，边编号为 $1$ 到 $m$。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。你需要计算该仙人掌图的连通性值。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$（$1\le n\le 100\,000$，$0\le m\le 200\,000$）。接下来的 $m$ 行中的第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1\le u_i<v_i\le n$）。输入表示一个仙人掌图，且任意一对顶点之间至多有一条边。

输出格式

输出给定图的连通性值。

4 3
1 2
2 3
1 3

3

3 0

1

提示

样例输入/输出 #1 的解释

这对应于题目描述中的图 $Z$。

样例输入/输出 #2 的解释

任意 $1$ 边连通的超图就是一个连通图。由于给定图没有边，从连通图中移除给定图的所有边后，该图仍然连通。

翻译由 DeepSeek 完成