不要成环

题目描述

给定一个有 $N$ 个顶点和 $M$ 条边的简单无向图。顶点编号为 $1$ 到 $N$,第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。

删除零条或多条边,使得图中不再含有环。求为此最少需要删除的边数。

什么是简单无向图?

没有自环、没有重边、且边没有方向的无向图称为简单无向图。

什么是环?

简单无向图中的环是长度至少为 $3$ 的顶点序列 $(v_0, v_1, \ldots, v_{n-1})$,满足:若 $i \neq j$ 则 $v_i \neq v_j$,并且对每个 $0 \leq i \lt n$,$v_i$ 与 $v_{i+1 \bmod n}$ 之间有边相连。

输入格式

输入按以下格式从标准输入给出:

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

输出格式

输出答案。

样例

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

2

使图无环的一种方法是删除顶点 $1$ 与顶点 $2$ 之间的边,以及顶点 $4$ 与顶点 $5$ 之间的边。

无法通过删除 1 条或更少的边使图无环,因此应输出 $2$。

4 2
1 2
3 4

0

5 3
1 2
1 3
2 3

1

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq N$
• 给定的图是简单图。
• 输入中的所有值均为整数。