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

问题描述

给你一个包含 $N$ 个顶点和 $M$ 条边的简单无向图。

顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。

我们需要删除零条或更多边，使得图中不存在环。

求必须删除的最少边数。

名词定义

什么是简单无向图？ 简单无向图是没有自环（顶点连接自身的边）、没有重边（同一对顶点间多条边），且边无方向的图。

什么是环？ 简单无向图中的环是一个长度至少为 $3$ 的顶点序列 $(v_0, v_1, \dots, v_{n-1})$，满足以下条件：

1. 所有顶点互不相同（即 $i \neq j$ 时 $v_i \neq v_j$）；
2. 对于每个 $0 \leq i < n$，顶点 $v_i$ 和 $v_{(i+1) \bmod n}$ 之间有边相连（首尾顶点也需相连）。

输入格式

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

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$...$

$A_M$ $B_M$

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

输出格式

输出需要删除的最少边数。

样例

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