分数: 350 点
问题陈述
给你一个简单的无向图 N 顶点和 M 边,其中顶点被标记 1 to N。的 i第一条边连接顶点 u_i 和 v_i.
需要从此图中删除最少多少条边才能使该图成为森林?
什么是森林?
一个简单的无向图 F 被称为森林当且仅当 F 不包含任何循环。约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq \min \left( \frac{N(N-1)}{2}, 2 \times 10^5\right)
- 1 \leq u_i < v_i \leq N
- 给定的图表很简单。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
输出
打印答案。
示例输入 1
4 4 1 2 1 3 2 4 3 4
示例输出 1
1
例如,如果删除第一条边,图形将变成森林。
示例输入 2
5 0
示例输出 2
0
示例输入 3
10 10 7 9 4 6 6 10 2 5 5 6 5 9 6 8 4 8 1 5 1 4
示例输出 3
2