#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const int N=1e5+50;
int n,m;
vector<pair<int,int>>edges;
struct DSU{
int par[N],sajz[N],bip;bool f[N];
vector<array<int,3>>undo;
DSU(){Init();}
void Init(){for(int i=1;i<N;i++)par[i]=i,sajz[i]=1,f[i]=0;bip=0;}
pair<int,bool>FS(int u){
if(u==par[u])return {u,false};
auto [v,x]=FS(par[u]);
return {v,x^f[u]};
}
bool US(int u,int v){
auto [u1,c1]=FS(u);
auto [u2,c2]=FS(v);
if(u1==u2){
int x=0;
if(c1==c2)x=1;
bip+=x;
undo.pb({u1,u2,x});
return false;
}
if(sajz[u1]>sajz[u2])swap(u1,u2),swap(c1,c2);
par[u1]=u2;
sajz[u2]+=sajz[u1];
f[u1]=c1^c2^1;
undo.pb({u1,u2,0});
return true;
}
void Undo(){
auto [u1,u2,x]=undo.back();undo.pop_back();
if(u1==u2)bip-=x;
else{
par[u1]=u1;
sajz[u2]-=sajz[u1];
f[u1]=0;
}
}
}dsu;
int Solve(int l,int r){
if(l>r)return 0;
int mid=l+r>>1;
for(int i=l;i<mid;i++)dsu.US(edges[i].fi,edges[i].se);
for(int i=mid+1;i<=r;i++)dsu.US(edges[i].fi,edges[i].se);
int res=0;
if(dsu.bip==0){
auto [u,v]=edges[mid];
auto [u1,c1]=dsu.FS(u);
auto [u2,c2]=dsu.FS(v);
if(u1!=u2||c1==c2)res++;//,printf("[%i %i]\n",edges[mid].fi,edges[mid].se);
}
for(int i=mid+1;i<=r;i++)dsu.Undo();
dsu.US(edges[mid].fi,edges[mid].se);
res+=Solve(mid+1,r);
for(int i=l;i<=mid;i++)dsu.Undo();
for(int i=mid;i<=r;i++)dsu.US(edges[i].fi,edges[i].se);
res+=Solve(l,mid-1);
for(int i=mid;i<=r;i++)dsu.Undo();
return res;
}
int main(){
scanf("%i%i",&n,&m);
for(int i=0;i<m;i++){
int u,v;scanf("%i%i",&u,&v);
edges.pb({u,v});
}
int res=Solve(0,m-1);
printf("%i\n",res);
return 0;
}
