Phylogenetic Tree

Working out how organisms are related is a basic task in bioinformatics. The relationship is usually drawn as a tree, called a phylogenetic tree.

Every organism is one leaf node of the phylogenetic tree. A node that does not stand for an organism is an internal node, and no edge joins two organisms directly. The length of the path between two leaf nodes says how close the two organisms are in evolutionary terms.

Keeping only the closeness between organisms gives a graph, called a phylogenetic graph. The phylogenetic graph of similarity $K$ is defined as follows. Its vertices are the organisms, and two vertices are joined by an edge if and only if the distance in the phylogenetic tree between the two matching leaf nodes, that is the length of the path, is at most $K$.

A laboratory built the phylogenetic graph of similarity 3 and then lost the data of the phylogenetic tree. Only the graph is left to reconstruct the tree from, and several phylogenetic trees may define the same graph. The goal is the size of the smallest of them, the tree with the fewest edges.

Given a phylogenetic graph of similarity 3, write a program that finds the number of edges of the phylogenetic tree with the fewest edges among those defining the graph. The given phylogenetic graph is always connected, and a phylogenetic tree defining it always exists.

The first line contains the number of vertices $N$ ($2 \le N \le 5000$) of the phylogenetic graph. The vertices are numbered 1 through $N$.

The second line contains the number of edges $M$ ($1 \le M \le 10^6$) of the phylogenetic graph.

Each of the next $M$ lines contains two integers $v$ and $w$ ($1 \le v, w \le N$), the two endpoints of one edge.

Print the number of edges $S$ of the phylogenetic tree with the fewest edges among those defining the given phylogenetic graph.