问题2439--srg不喜欢循环

2439: srg不喜欢循环

[命题人 : ]
时间限制 : 3 sec  内存限制 : 128 MB

提交

题目描述

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

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

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

输入

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

输出

输出删除最少的边数。

样例输入 Copy

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

样例输出 Copy

2