CF51F.Caterpillar

An undirected graph is called a caterpillar if it is a connected graph without cycles and it has such a path p that any vertex is located at a distance of at most 1 from the path p. The caterpillar can contain loops (edges from a vertex to itself) but cannot contain multiple (parallel) edges.

The picture contains an example of a caterpillar:

You are given an undirected graph G. You are allowed to do a merging operations, each such operation merges two vertices into one vertex. For that two any vertices a and b (a ≠ b) are chosen. These verteces are deleted together with their edges (which are incident to at least one of the vertices a or b) but a new vertex w is added together with edges (x, w) for each edge (a, w) and/or (b, w). If there was the edge (a, b) it transforms to the loop (w, w). The resulting graph (after the merging operation) may contain multiple (parallel) edges between pairs of vertices and loops. Let us note that this operation decreases the number of vertices of graph by 1 but leaves the number of edges in the graph unchanged.

The merging operation can be informally described as a unity of two vertices of the graph into one with the natural transformation of the graph edges.

You may apply this operation consecutively and make the given graph to be a caterpillar. Write a program that will print the minimal number of merging operations required to make the given graph a caterpillar.

无向图被称为“毛虫图”，当且仅当它是一个连通的无环图，且存在一条路径 $p$，使得图中任意顶点到该路径 $p$ 的距离至多为 1。毛虫图可以包含自环（即从一个顶点连向其自身的边），但不能包含多重边（即平行边）。

下图展示了一个毛虫图的例子：

给定一个无向图 $G$。你被允许执行“合并”操作，每次操作将两个顶点合并为一个顶点。具体地，任选两个不同顶点 $a$ 和 $b$（$a \ne b$），删除这两个顶点以及所有与至少其中一个顶点 $a$ 或 $b$ 关联的边；同时添加一个新顶点 $w$，并对每个原图中存在的边 $(a, w)$ 或 $(b, w)$，均在新图中加入边 $(x, w)$（注意：此处 $x$ 应理解为原边另一端点，即若存在边 $(a, u)$ 或 $(b, u)$，则加入边 $(u, w)$）；若原图中存在边 $(a, b)$，则它变为新顶点 $w$ 上的一个自环 $(w, w)$。执行一次合并操作后所得的图可能包含顶点对之间的多重边及自环。需注意，该操作使图的顶点数减少 1，但边数保持不变。

合并操作可直观理解为：将图中两个顶点自然地“融合”为一个顶点，并相应调整所有关联边。

你可以连续执行该操作，使给定图最终变为一个毛虫图。请编写程序，输出将给定图变为毛虫图所需的最少合并操作次数。

The first line contains a pair of integers n, m (1 ≤ n ≤ 2000;0 ≤ m ≤ 105), where n represents the number of vertices in the graph and m is the number of edges in it. Then the following m lines contain edge descriptions, one edge description per line. Every line contains a pair of integers a__i, b__i (1 ≤ a__i, b__i ≤ n;a__i ≠ b__i), a__i, b__i which represent the indices of the vertices connected by the edge. The vertices are numbered from 1 to n. In the given graph it will be no more than one edge between any pair of vertices. The given graph is not necessarily connected.

第一行包含一对整数 $n$、$m$（$1 \leq n \leq 2000$；$0 \leq m \leq 10^5$），其中 $n$ 表示图中顶点的数量，$m$ 表示图中边的数量。接下来的 $m$ 行每行描述一条边。每行包含一对整数 $a_i,\,b_i$（$1 \leq a_i,\,b_i \leq n$；$a_i \neq b_i$），表示该边所连接的两个顶点的编号。顶点编号从 $1$ 到 $n$。给定图中任意一对顶点之间至多只有一条边。给定图不一定是连通的。

Print the minimal required number of operations.

输出所需的最少操作次数。