Redundant Paths

Problem Source

USACO 2006 Jan

Problem Description

You are given an undirected connected graph with $n$ vertices and $m$ edges. What is the minimum number of edges you must add so that the graph becomes edge-biconnected (i.e. there remain no bridge edges)?

Input Format

The first line contains two integers $n, m$ ($1 \leq n \leq 5000,\ 1 \leq m \leq 10^4$).

The next $m$ lines each contain two integers $u, v$, indicating an undirected edge.

Output Format

Output one integer: the answer.

Sample Input

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

Sample Output

2

Constraints

• $1 \leq n \leq 5000$
• $1 \leq m \leq 10^4$