← 返回题目列表

AtCoder · abc399_c

F. 让它成为森林

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

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