← 返回题目列表

AtCoder · abc393_c

F. 让它变得简单

中文机器翻译题面 查看原题

分数: 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