Codeforces Round #416 (Div. 2) has been moved to start on 27.05.2017 09:35 (UTC).
×

Package for this problem was not updated by the problem writer or Codeforces administration after we’ve upgraded the judging servers. To adjust the time limit constraint, solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then value 800 ms will be displayed and used to determine the verdict.

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. Caterpillar

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputAn 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.

Input

The first line contains a pair of integers *n*, *m* (1 ≤ *n* ≤ 2000;0 ≤ *m* ≤ 10^{5}), 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.

Output

Print the minimal required number of operations.

Examples

Input

4 4

1 2

2 3

3 4

4 2

Output

2

Input

6 3

1 2

3 4

5 6

Output

2

Input

7 6

1 2

2 3

1 4

4 5

1 6

6 7

Output

1

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/26/2017 19:50:23 (c4).

Desktop version, switch to mobile version.
User lists

Name |
---|