分数: 300 点
问题陈述
给你一个简单的无向图 N 顶点和 M 边缘。顶点已编号 1 to N,以及 i第一条边连接顶点 A_i 和顶点 B_i。 让我们删除零个或多个边以从图中删除循环。找出为此目的必须删除的最小边数。
什么是简单无向图?
一个简单的无向图 是一个没有自环或边没有方向的多边图。
什么是循环?
A 循环
图表的 简单无向图中是一系列顶点
长度至少为 (v_0, v_1, \ldots, v_{n-1}) 至少长度 3 满意 v_i \neq v_j if i \neq 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