Problem2439--srg不喜欢循环

2439: srg不喜欢循环

[Creator : ]
Time Limit : 3.000 sec  Memory Limit : 128 MiB

Description

给你一个简单的无向图,图中有 N 个顶点和 M 条边。顶点的编号为 1 到 N , i 条边连接顶点 Ai 和顶点 Bi 。让我们删除零条或更多条边,以消除图中的循环。求为此目的必须删除的最小边数。

什么是简单无向图?简单无向图是没有自循环或多条边的图,其边没有方向。

什么是循环?简单无向图中的周期是长度至少为 3 的顶点 (v0,v1,…,vn−1) 序列,满足vi ≠ vj ,如果 i≠j ,则对于每个 0≤i<n , vi 和 vi+1modn 之间都有一条边。

Input

输入一个N,M。( 1≤N≤2×105 ,0≤M≤2×105 
输入 M 行的 Ai,Bi。( 1≤Ai,Bi≤N )

Output

输出删除最少的边数。

Sample Input Copy

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

Sample Output Copy

2

Source/Category

admin