题目大概说要让n个骑士坐成一圈，这一圈的人数要是奇数且大于2，此外有些骑士之间有仇恨不能坐在一起，问有多少个骑士不能入座。
双连通图上任意两点间都有两条不重复点的路径，即一个环。那么，把骑士看做点，相互不仇恨的骑士间连边，能坐在一圈骑士的肯定在同一个点双连通分量上。
不过还有个条件是人数要大于2：
- 有这么一个结论：如果一个双连通分量存在奇圈（点数为奇数的环），那么这个双连通分量里所有点一定会包含在某一个奇圈内。
- 大概是因为，双连通分量里面点为奇数个显然都包含在奇圈里；而如果是偶数个，一部分就包含在那个找到的奇圈，而剩下的偶数-奇数=奇数个点一定也形成一个奇圈。
- 这样只要判断双连通分量是否存在奇圈即可。而存在奇圈是图是否为二分图的充分必要条件，而判断是否为二分图可以用染色法。
因此这题就是找双连通分量，找到一个双连通分量后，染色判断它是否包含奇圈，如果是双连通分量内所有点都能入座。
要注意的是一个点能属于多个点双连通分量。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 1111
#define MAXM 1111111
struct Edge{
int v,flag,next;
}edge[MAXM<<];
int NE,head[MAXN];
void addEdge(int u,int v){
edge[NE].v=v; edge[NE].flag=;
edge[NE].next=head[u]; head[u]=NE++;
} int n,ans[MAXN]; int dn,dfn[MAXN],low[MAXN];
int stack[MAXM],top;
int tag[MAXN],color[MAXN]; bool dfs(int u){
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(!tag[v]) continue;
if(color[v]==color[u]) return ;
if(color[v]==-){
color[v]=!color[u];
return dfs(v);
}
}
return ;
} void tarjan(int u){
dfn[u]=low[u]=++dn;
for(int i=head[u]; i!=-; i=edge[i].next){
if(edge[i].flag) continue;
edge[i].flag=edge[i^].flag=;
stack[++top]=i; int v=edge[i].v; if(dfn[v]){
low[u]=min(low[u],dfn[v]);
continue;
} tarjan(v);
low[u]=min(low[u],low[v]); if(low[v]>=dfn[u]){
memset(tag,,sizeof(tag));
int k;
do{
k=stack[top--];
tag[edge[k].v]=;
tag[edge[k^].v]=;
}while(edge[k^].v!=u);
memset(color,-,sizeof(color));
color[u]=;
if(dfs(u)){
for(int i=; i<=n; ++i){
if(tag[i]) ans[i]=;
}
}
}
}
} bool ishate[MAXN][MAXN];
int main(){
int m;
while(~scanf("%d%d",&n,&m) && (n||m)){
memset(ishate,,sizeof(ishate));
int a,b;
while(m--){
scanf("%d%d",&a,&b);
ishate[a][b]=ishate[b][a]=;
} NE=;
memset(head,-,sizeof(head));
for(int i=; i<=n; ++i){
for(int j=i+; j<=n; ++j){
if(i==j) continue;
if(!ishate[i][j]){
addEdge(i,j);
addEdge(j,i);
}
}
} memset(ans,,sizeof(ans));
dn=; memset(dfn,,sizeof(dfn));
top=;
for(int i=; i<=n; ++i){
if(dfn[i]==) tarjan(i);
} int res=;
for(int i=; i<=n; ++i){
if(!ans[i]) ++res;
}
printf("%d\n",res);
}
return ;
}