← 返回题目列表

AtCoder · abc288_c

F. 不要循环

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

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