#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<<1],col[N],sz[N],cnt; struct{ int hd[N],to[maxn<<1],nxt[maxn<<1],tot=1; void link(int x,int y){ ++tot;to[tot]=y,nxt[tot]=hd[x],hd[x]=tot; } }G; int ex[maxn],ey[maxn],deg[N],tot[N]; void dfs(int u,int fa){ dfn[u]=low[u]=++cnt; for(int i=G.hd[u];i;i=G.nxt[i])if((i^1)!=fa){ if(!dfn[G.to[i]]){ dfs(G.to[i],i); if(low[G.to[i]]>=dfn[u])is[i]=is[i^1]=1; low[u]=min(low[u],low[G.to[i]]); }else low[u]=min(low[u],dfn[G.to[i]]); } } int q[maxn]; void bfs(int u,int c){ int L=1,R=1;col[u]=c;q[1]=u; while(L<=R){ u=q[L++];++sz[c]; for(int i=G.hd[u];i;i=G.nxt[i])if((!is[i])&&(!col[G.to[i]]))col[G.to[i]]=c,q[++R]=G.to[i]; } } void slv(){ n=read(),m=read(); up(i,1,m)ex[i]=read(),ey[i]=read(),G.link(ex[i],ey[i]),G.link(ey[i],ex[i]); up(i,1,n)if(!dfn[i])dfs(i,0); up(i,1,n)if(!col[i])bfs(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; }