该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

C - 消除环

分数：300分

问题描述

给定一个具有$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 < n$，$v_i$和$v_{i+1 \bmod n}$之间都有一条边。

约束条件

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

输入

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

输出

打印答案。

样例输入1

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

样例输出1

2

一种消除图中环的方法是删除顶点$1$和顶点$2$之间的边以及顶点$4$和顶点$5$之间的边。无法通过删除一条或更少的边来消除图中的环，因此应输出$2$。

样例输入2

4 2
1 2
3 4

样例输出2

0

样例输入3

5 3
1 2
1 3
2 3

样例输出3

1