#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <stack> using namespace std; const int maxn = 1100; struct node{ int x,y; node(int x=0,int y=0):x(x),y(y){} }; int pre[maxn],bccno[maxn],dfs_clock,bcc_cnt,iscut[maxn],n,m; vector<int> son[maxn],bcc[maxn]; stack<node> S; int dfs(int u,int fa){ int lowu,lowv; lowu=pre[u]=++dfs_clock; int child=0; for(int i=0;i<son[u].size();i++)if(son[u][i]!=fa){ int v=son[u][i]; if(!pre[v]){ child++; S.push(node(u,v)); lowv=dfs(v,u); lowu=min(lowv,lowu); if(pre[u]<=lowv){ iscut[u]=true; bcc[bcc_cnt].clear(); for(;;){ node te=S.top(); S.pop(); if(bccno[te.x]!=bcc_cnt){ bccno[te.x]=bcc_cnt; bcc[bcc_cnt].push_back(te.x); } if(bccno[te.y]!=bcc_cnt){ bccno[te.y]=bcc_cnt; bcc[bcc_cnt].push_back(te.y); } if(te.x==u && te.y ==v) break; } bcc_cnt++; } } else if(pre[v]<pre[u]){ S.push(node(u,v)); lowu=min(lowu,pre[v]); } } if(fa==-1&&child==1) iscut[u]=0; return lowu; } void find_bcc(int n){ memset(pre,0,sizeof(pre)); memset(iscut,0,sizeof(iscut)); memset(bccno,-1,sizeof(bccno)); dfs_clock=bcc_cnt=0; for(int i=1;i<=n;i++){ if(!pre[i]) dfs(i,-1); } } int color[maxn]; bool btripartite(int u,int belong){ for(int i=0;i<son[u].size();i++) if(bccno[son[u][i]]==belong||iscut[son[u][i]]){ int v=son[u][i]; if(color[v]){ if(color[v]==color[u]) return false; } else { color[v]=3-color[u]; btripartite(v,belong); } } return true; } int odd[maxn]; int vis[maxn]; int main() { while(scanf("%d %d",&n,&m)==2){ if(!n&&!m) break; for(int i=1;i<=n;i++) son[i].clear(); while(m--){ int x,y; scanf("%d %d",&x,&y); son[x].push_back(y); son[y].push_back(x); } for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); for(int j=0;j<son[i].size();j++) vis[son[i][j] ]=1; son[i].clear(); //cout<<i<<": "; for(int j=1;j<=n;j++) if(!vis[j]&&i!=j){ son[i].push_back(j); //cout<<j<<" "; } //cout<<endl; } find_bcc(n); memset(odd,0,sizeof(odd)); for(int i=0;i<bcc_cnt;i++){ memset(color,0,sizeof(color)); color[bcc[i][0]]=1; if(!btripartite(bcc[i][0],i)){ for(int j=0;j<bcc[i].size();j++) odd[bcc[i][j] ]=1; } } int res=0; for(int i=1;i<=n;i++) if(!odd[i]) res++; printf("%d\n",res); } return 0; }