#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } const int N=4e6+10,maxn=1e7+10; int n,m,dfn[N],low[N],is[maxn],col[N],sz[N],cnt; vector<pi>E[N]; int ex[maxn],ey[maxn],deg[N],tot[N]; void dfs(int u,int fa){ dfn[u]=low[u]=++cnt; for(auto it:E[u])if(it.p2!=fa){ if(!dfn[it.p1]){ dfs(it.p1,it.p2); if(low[it.p1]>=dfn[u])is[it.p2]=1; low[u]=min(low[u],low[it.p1]); }else low[u]=min(low[u],dfn[it.p1]); } } void dfs2(int u,int c){ col[u]=c;++sz[c]; for(auto it:E[u])if((!col[it.p1])&&(!is[it.p2]))dfs2(it.p1,c); } void slv(){ n=read(),m=read(); up(i,1,m)ex[i]=read(),ey[i]=read(),E[ex[i]].p_b({ey[i],i}),E[ey[i]].p_b({ex[i],i}); up(i,1,n)if(!dfn[i])dfs(i,0); up(i,1,n)if(!col[i])dfs2(i,++col[0]); up(i,1,m)if(col[ex[i]]!=col[ey[i]])++deg[ex[i]],++deg[ey[i]]; up(i,1,n)if(deg[i]>0)++tot[col[i]]; int res=0,c=0; up(i,1,col[0])res+=sz[i]>1&&tot[i]<=1; up(i,1,n)if(deg[i]&1)c++;res+=c/2; cout<<res; } int main(){ //freopen("graph.in","r",stdin),freopen("graph.out","w",stdout); slv(); return 0; }