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

// Problem: P2860 [USACO06JAN]Redundant Paths G
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2860
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back

const int maxn = 5e3 + 5;
std::vector<std::pair<int,int> > G[maxn];
int n,m,low[maxn],dfn[maxn],cnt,tot,col[maxn],stk[maxn],tp,deg[maxn];

void form(int u) {
	++ tot;
	for(int x = 0;x != u;)
		col[x = stk[tp --]] = tot;
	return ;
}

void tarjan(int u,int lst) {
	stk[++ tp] = u;
	dfn[u] = low[u] = ++ cnt;
	for(auto& p : G[u]) {
		int v = p.first,id = p.second;
		if(id == lst)continue ;
		if(!dfn[v]) {
			tarjan(v , id);
			low[u] = std::min(low[u] , low[v]);
			if(low[v] > low[u])
				form(v);
		}
		else
			low[u] = std::min(low[u] , dfn[v]);
	}
	if(!lst)
		form(u);
	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 u,v;
		scanf("%d %d",&u,&v);
		G[u].pb(v , i);
		G[v].pb(u , i);
	}
	
	tarjan(1 , 0);
	
	for(int i = 1;i <= n;++ i) {
		for(auto& p : G[i]) {
			int v = p.first;
			if(i < v&&col[i] != col[v])
				++ deg[col[i]],++ deg[col[v]];
		}
	}
	int cnt = 0;
	for(int i = 1;i <= tot;++ i)
		cnt += deg[i] == 1;
	
	printf("%d\n",(cnt + 1) >> 1);
	return 0;
}