Score : $300$ points

问题陈述

给定一个包含 $N$ 个顶点和 $M$ 条边的简单无向图。顶点编号为 $1$ 到 $N$，第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$。我们需要删除零个或多个边以去除图中的环路。请找出为了达到此目的必须删除的最少边数。

什么是简单无向图？简单无向图是一种没有自环和平行边、且边无方向的图。

什么是环路？在简单无向图中，环路是指长度至少为 $3$ 的顶点序列 $(v_0, v_1, \ldots, v_{n-1})$，满足当 $i \neq j$ 时有 $v_i \neq v_j$，并且对于每个 $0 \leq i < n$，存在一条连接顶点 $v_i$ 和 $v_{(i+1) \bmod n}$ 的边。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a simple undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ to $N$, and the $i$-th edge connects vertex $A_i$ and vertex $B_i$. Let us delete zero or more edges to remove cycles from the graph. Find the minimum number of edges that must be deleted for this purpose.

What is a simple undirected graph? A simple undirected graph is a graph without self-loops or multi-edges whose edges have no direction.

What is a cycle? A cycle in a simple undirected graph is a sequence of vertices $(v_0, v_1, \ldots, v_{n-1})$ of length at least $3$ satisfying $v_i \neq v_j$ if $i \neq j$ such that for each $0 \leq i < n$, there is an edge between $v_i$ and $v_{i+1 \bmod n}$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq M \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq N$
• The given graph is simple.
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$ $M$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_M$ $B_M$

Output

Print the answer.

Sample Input 1

6 7
1 2
1 3
2 3
4 2
6 5
4 6
4 5

Sample Output 1

2

One way to remove cycles from the graph is to delete the two edges between vertex $1$ and vertex $2$ and between vertex $4$ and vertex $5$.
There is no way to remove cycles from the graph by deleting one or fewer edges, so you should print $2$.

Sample Input 2

4 2
1 2
3 4

Sample Output 2

0

Sample Input 3

5 3
1 2
1 3
2 3

Sample Output 3

1

update @ 2024/3/10 12:01:52