记录编号	577661	评测结果	AAAAAAAAAAAAAAAAA
题目名称	[USACO Jan06 Gold] 冗余路径(Redundant Paths)	最终得分	100
用户昵称	op_组撒头屯	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-11-20 12:51:43	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=5000+5;
const int M=10000+5;
struct sdf{
	int to,next;
}eg[2*M],br[M];
int head[N],ne=1;
int n,m;
void add(int x,int y){
	eg[++ne]={y,head[x]};
	head[x]=ne;return ;
}
int dfn[N],low[N],tim=0,tot=0;
bool isbr[2*M];
void dfs(int pt,int lst){
	dfn[pt]=low[pt]=++tim;
	for (int i=head[pt];i!=0;i=eg[i].next){
		int v=eg[i].to;
		if (!dfn[v]){
			dfs(v,i);
			low[pt]=min(low[pt],low[v]);
			if (dfn[pt]<low[v])isbr[i]=isbr[i^1]=1,br[++tot]={pt,v};
		}
		else if (i!=(lst^1))low[pt]=min(low[pt],dfn[v]);
	}
	return ;
}
int id[N],cnt=0,deg[N]={0};
void dfs2(int pt){
	id[pt]=cnt;
	for (int i=head[pt];i!=0;i=eg[i].next){
		int v=eg[i].to;
		if (isbr[i]||id[v])continue;
		dfs2(v);
	}
	return ;
}
int main(){
	freopen ("rpaths.in","r",stdin);
	freopen ("rpaths.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(1,0);
	for (int i=1;i<=n;i++){
		if (!id[i])cnt++,dfs2(i);
	}
	for (int i=1;i<=tot;i++){
		int x=br[i].to,y=br[i].next;
		deg[id[x]]++;deg[id[y]]++;
	}
	int ans=0;
	for (int i=1;i<=cnt;i++){
		if (deg[i]==1)ans++;
	}
	printf("%d\n",(ans+1)/2);
	return 0;
}