Königsberg Bridges

Time limit3sMemory limit512 MB

Summary

Given a graph, add edges so that a simple path passes through every bridge, and find the maximum number of bridges possible.

Level: Medium7 of 10
Topics: Graph, DFS, Tree
Solved: No attempts yet

Problem

Given a graph, we say it is Königsbergsy if there is a simple path that goes through all of its bridges. Here, a bridge is an edge that disconnects the graph when removed. A simple path is a path that visits each vertex at most once.

Given a graph $G$ , add some edges to it to make it Königsbergsy. You may add more than one edge between the same pair of vertices. Determine the maximum number of bridges that the resulting graph can have.

Input

The first line contains two integers $n$ and $m$ ( $2 \leq n \leq 10^6$ ; $0 \leq m \leq 10^6$ ), the number of vertices and the number of edges of $G$ .

Each of the next $m$ lines contains two integers $u_i$ , $v_i$ ( $0 \leq u_i, v_i \leq n-1$ ), describing an edge between vertices $u_i$ and $v_i$ .

Output

Output one integer, the maximum number of bridges the resulting graph can have.

Examples2

Example 1
Input
```
4 3
0 1
1 2
2 0
```
Expected output
```
1
```
Example 2
Input
```
4 2
0 1
1 2
```
Expected output
```
3
```