由于互相憎恨的骑士不能相邻，把可以相邻的骑士连上无向边，会议要求是奇数，问题就是求不在任意一个简单奇圈上的结点个数。
如果不是二分图，一定存在一个奇圈，同一个双连通分量中其它点一定可以加入奇圈。很明显，其它点和已知的奇圈相连总是有两条点数一奇一偶的路径，
因此一定可以找到一条回路使得新的这个点加入一个奇圈。
#include<bits/stdc++.h>
using namespace std;
#define bug(x) cout<<#x<<'='<<x<<endl;
const int maxv = +;
const int maxe = maxv*maxv;//开小 int dfn[maxv],low[maxv],bccno[maxv],dfs_clock,bcc_cnt;
bool iscut[maxv];
vector<int> bcc[maxv];
int head[maxv],fro[maxe],to[maxe],nxt[maxe],ecnt; int edges[maxe],top; void addEdge(int u,int v)
{
fro[ecnt] = u;
to[ecnt] = v;
nxt[ecnt] = head[u];
head[u] = ecnt++;
} void tarjan(int u,int fa)
{
dfn[u] = low[u] = ++dfs_clock;
for(int i = head[u]; ~i; i = nxt[i]){
int v = to[i]; if(!dfn[v]){
edges[++top] = i;
tarjan(v,i);
low[u] = min(low[v],low[u]);
if(low[u] >= dfn[u]){
iscut[u] = true;
bcc_cnt++; bcc[bcc_cnt].clear(); //bcc从1开始
int U,V;
do{
int e = edges[top--];
U = fro[e], V = to[e];
if(bccno[U] != bcc_cnt) { bcc[bcc_cnt].push_back(U); bccno[U]=bcc_cnt; }
if(bccno[V] != bcc_cnt) { bcc[bcc_cnt].push_back(V); bccno[V]=bcc_cnt; }
}while(U!=u||V!=v);
}
}else if((i^) != fa && dfn[v] < dfn[u] ){ low[u] = min(low[u],dfn[v]); edges[++top] = i; }// == 比 ^优先级高！第二个条件少了会WA是什么原因
}
} void find_bcc(int n)
{
top = ;
memset(dfn ,,sizeof(dfn));
memset(iscut, ,sizeof(iscut));
memset(bccno, ,sizeof(bccno));
dfs_clock = bcc_cnt = ;
for(int i = ; i < n; i++) {
if(!dfn[i]) {
tarjan(i,-);
iscut[i] = ~nxt[head[i]];// !(nxt[head[i]] == -1);//树根特判,如果只有一个子结点false
}
}
} int color[maxv];
bool bipartite(int u, int b)
{
for(int i = head[u]; ~i; i = nxt[i]){
int v = to[i]; if(bccno[v] != b) continue;
if(color[v] == color[u]) return false;
if(!color[v]){
color[v] = - color[u];
if(!bipartite(v,b)) return false;
}
}
return true;
} bool hate[maxv][maxv];
bool inOdd[maxv]; int main()
{
//freopen("in.txt","r",stdin);
int n,m;
while(~scanf("%d%d",&n,&m)&&(n||m)){
memset(hate,,sizeof(hate));
while(m--){
int u,v; scanf("%d%d",&u,&v); u--,v--;
hate[u][v] = hate[v][u] = true;
}
memset(head,-,sizeof(head)); ecnt = ;
for(int i = ; i < n; i++)
for(int j = i+; j < n; j++) if(!hate[i][j]){
addEdge(i,j); addEdge(j,i);
}
find_bcc(n);
// bug(bcc_cnt);
memset(inOdd,,sizeof(inOdd));
for(int i = ; i <= bcc_cnt; i++){
memset(color,,sizeof(color));
for(int j = ; j < bcc[i].size(); j++) bccno[bcc[i][j]] = i; //割点，属于多个连通分量，因此特殊处理
int u = bcc[i][];
color[u] = ;
if(!bipartite(u,i)){
for(int j = ; j < bcc[i].size(); j++) inOdd[bcc[i][j]] = true;
}
}
int ans = n;
for(int i= ; i < n; i++) if(inOdd[i]) ans--;
printf("%d\n",ans);
}
return ;
}