分数: 300 点
问题陈述
给你一个无向图 N 顶点和 M 边,其中顶点编号 1 通过 N 且边缘已编号 1 通过 M。边缘 i 连接顶点 u_i 和 v_i.
为了通过删除边使图变得简单,必须删除的边的最小数量是多少?
这里,当且仅当一个图不包含自环或多边时,该图才被称为简单图。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 5 \times 10^5
- 1 \leq u_i \leq N
- 1 \leq v_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
输出
打印为使图形简单而必须删除的最小边数。
示例输入 1
3 5 1 2 2 3 3 2 3 1 1 1
示例输出 1
2
通过删除边缘 3 和 5,图表变得简单。这是去除最少边数的方法之一,所以答案是 2.
示例输入 2
1 0
示例输出 2
0
示例输入 3
6 10 6 2 4 1 5 1 6 6 5 3 5 1 1 4 6 4 4 2 5 6
示例输出 3
3