#include using namespace std; const int N=1e5+10; struct graph{ vector>adj[N]; vector>rin[N]; vectorvis,vis2,vis3,odd; int tot,cnt; graph():tot(0),cnt(0){ vis.clear(); vis2.clear(); vis3.clear(); } void add_edge(int u,int v) { adj[u].push_back(make_pair(v,++tot)); adj[v].push_back(make_pair(u,tot)); } void add() { for(int i=0;i=1){ pair v=adj[u].back(); adj[u].pop_back(); if(vis2[v.second]==1)continue; if(flag==1)cnt++; pairtest=make_pair(u,v.first); rin[cnt].push_back(make_pair(u,v.first)); vis2[v.second]=1; dfs2(v.first,p); flag=1; } if(flag==0&&rin[cnt].size()%2==1)p++,rin[cnt].push_back(make_pair(u,u)); } }gra; int main(){ int n,m; cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; gra.add_edge(u,v); } gra.vis.resize(n+1); gra.vis2.resize(gra.tot+1); gra.vis3.resize(n+1); for(int i=1;i<=n;i++)if(gra.vis[i]==0)gra.odd.clear(),gra.dfs(i),gra.add(); int p=gra.tot; for(int i=1;i<=n;i++)if(gra.vis3[i]==0)gra.cnt++,gra.dfs2(i,p); cout<