#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; bool ST; namespace IO { inline char nc() { static char buf[500001], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 500000, stdin), p1 == p2) ? EOF : *p1++; } inline int read() { char ch = nc(); int x = 0; for (; ch < '0' || ch > '9'; ch = nc()); while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = nc(); return x; } } using namespace IO; const int N=4e6+10,maxn=1e7+10; int n,m,dfn[N],low[N],col[N],sz[N],cnt; bool is[maxn<<1]; 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 deg[N],tot[N]; tuple<int,int,int,int>stk[maxn]; void dfs(int u){ int top=1;stk[1]=make_tuple(u,0,G.hd[u],0); auto upd=[&](int u){dfn[u]=low[u]=++cnt;};upd(u); while(top){ auto it=stk[top--]; int u=get<0>(it),fa=get<1>(it),i=get<2>(it); if((i^1)!=fa){ if(get<3>(it)){ low[u]=min(low[u],low[G.to[i]]); if(low[G.to[i]]>=dfn[u])is[i]=is[i^1]=1; if(G.nxt[i])stk[++top]=make_tuple(u,fa,G.nxt[i],0); } else if(dfn[G.to[i]]){ low[u]=min(low[u],dfn[G.to[i]]); if(G.nxt[i])stk[++top]=make_tuple(u,fa,G.nxt[i],0); }else { stk[++top]=make_tuple(u,fa,i,1); upd(G.to[i]);stk[++top]=make_tuple(G.to[i],i,G.hd[G.to[i]],0); } } else if(G.nxt[i])stk[++top]=make_tuple(u,fa,G.nxt[i],0); } } 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){ int x=read(),y=read();++deg[x],++deg[y]; G.link(x,y),G.link(y,x); }up(i,1,n)if(!dfn[i])dfs(i); up(i,1,n)if(!col[i])bfs(i,++col[0]); up(i,1,n)if(deg[i]>2)++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; } bool ED; int main(){ cerr<<((&ST)-(&ED))/1024.0/1024.0<<"\n"; //freopen("graph.in","r",stdin),freopen("graph.out","w",stdout); slv(); return 0; }