← 返回题目列表

Codeforces · 51/F

F. 卡特彼勒

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

如果一个无向图是一个无环的连通图,并且它的路径 p 使得任何顶点与路径 p 的距离最多为 1,则该无向图称为毛毛虫图。毛毛虫可以包含环(从顶点到自身的边),但不能包含多个(平行)边。

图片包含毛毛虫的示例:

给你一个无向图G。你可以进行合并操作,每个这样的操作将两个顶点合并成一个顶点。为此,选择两个任意顶点 a 和 b (a ≠ b)。这些顶点与其边(与顶点 a 或 b 中的至少一个相关)一起被删除,但对于每条边(a,w)和/或(b,w),将新顶点 w 与边(x,w)一起添加。如果存在边 (a, b),则它会转换为循环 (w, w)。生成的图(合并操作后)可能包含顶点对和循环之间的多个(平行)边。请注意,此操作将图的顶点数减少 1,但图中的边数保持不变。

合并操作可以非正式地描述为通过图边的自然变换将图的两个顶点合二为一。

您可以连续应用此操作并使给定的图形成为毛毛虫。编写一个程序,打印使给定图成为毛毛虫所需的最少合并操作数。

输入

第一行包含一对整数 n, m (1 ≤ n ≤ 2000;0 ≤ m ≤ 105),其中 n 表示图中的顶点数,m 是图中的边数。然后接下来的 m 行包含边缘描述,每行一个边缘描述。每行包含一对整数 ai, bi (1 ≤ ai, bi ≤ n;ai ≠ bi), ai, bi 表示由边连接的顶点的索引。顶点编号为 1 到 n。在给定的图中,任意一对顶点之间最多只有一条边。给定的图不一定是连通的。

输出

打印所需的最少操作次数。

示例

输入 #1

4 4
1 2
2 3
3 4
4 2

输出 #1

2

输入 #2

6 3
1 2
3 4
5 6

输出 #2

2

输入 #3

7 6
1 2
2 3
1 4
4 5
1 6
6 7

输出 #3

1