#include <cstring> #include <algorithm> #include <iostream> #include <stack> using namespace std; const int N=5005; const int M=20005; int n, m; int head[N], E=0; int dfn[N], low[N], ts=0; stack<int> st; int id[N], ebcc_cnt=0; // 边双连通分量计数 bool is_bridge[N]; int d[N]; // 统计点的度数 struct Edge{int v, ne;}e[M]; inline void add(int a, int b){ e[E].v=b; e[E].ne=head[a]; head[a]=E++; } void tarjan(int u, int from){ dfn[u]=low[u]=++ts; st.push(u); for(int i=head[u]; ~i; i=e[i].ne){ int v=e[i].v; if(!dfn[v]){ // 如果是树枝边 tarjan(v, i); low[u]=min(low[u], low[v]); if(dfn[u]<low[v]){ // 连续的较小的偶数和较大的奇数构成桥, (0, 1), (2,3), (4,5) is_bridge[i]=is_bridge[i^1]=true; } } else if(i!=(from^1)){ // 如果不是反向边更新low[u] low[u]=min(low[u], dfn[v]); } } if(dfn[u]==low[u]){ ++ebcc_cnt; int j; do{ j=st.top(); st.pop(); id[j]=ebcc_cnt; }while(j!=u); } } int main(){ cin>>n>>m; memset(head, -1, sizeof head); while(m--){ int a, b; // 建立无向图 cin>>a>>b; add(a, b); add(b, a); } tarjan(1, -1); for(int i=0; i<E; ++i){ if(is_bridge[i]) d[id[e[i].v]]++; } // 统计缩点后度数为1的点 // 根据结论计算, 需要添加边的数量为(cnt+1)/2 int cnt=0; for(int i=1; i<=ebcc_cnt; ++i) if(d[i]==1) ++cnt; cout<<(cnt+1)/2<<endl; return 0; }