Don’t be cycle

题目描述

你被给定了一个包含 $N$ 个顶点和 $M$ 条边的简单无向图。顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。 让我们删除零条或多条边以从图中去除所有环。求为此必须删除的最小边数。

输入格式

输入按下述格式从标准输入给出： $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

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$ 给定的图是简单图。 输入中的所有数值均为整数。一种去除图中环的方法是删除连接顶点 $1$ 和顶点 $2$ 的两条边以及连接顶点 $4$ 和顶点 $5$ 的边。
不可能通过删除不超过一条边来去除图中的环，因此你应当输出 $2$。

标签: AtCoder|abc288C

来源

AtCoder|abc288C