Score : $300$ points

Problem Statement

You are given a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$, and the $i$-th edge connects vertex $A_i$ and vertex $B_i$. Let us delete zero or more edges to remove cycles from the graph. Find the minimum number of edges that must be deleted for this purpose.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq N$
• The given graph is simple.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_M$ $B_M$

Output

Print the answer.

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

2

One way to remove cycles from the graph is to delete the two edges between vertex $1$ and vertex $2$ and between vertex $4$ and vertex $5$. There is no way to remove cycles from the graph by deleting one or fewer edges, so you should print $2$.

4 2
1 2
3 4

0

5 3
1 2
1 3
2 3

1