題意：
亞瑟王要在圓桌上召開騎士會議，為了不引發騎士之間的沖突，並且能夠讓會議的議題有令人滿意的結果，每次開會前都必須對出席會議的騎士有如下要求：
1、 相互憎恨的兩個騎士不能坐在直接相鄰的2個位置；
2、 出席會議的騎士數必須是奇數，這是為了讓投票表決議題時都能有結果。
如果出現有某些騎士無法出席所有會議（例如這個騎士憎恨所有的其他騎士），則亞瑟王為了世界和平會強制把他剔除出騎士團。
現在給定准備去開會的騎士數n，再給出m對憎恨對（表示某2個騎士之間使互相憎恨的），問亞瑟王至少要剔除多少個騎士才能順利召開會議？
注意：1、所給出的憎恨關系一定是雙向的，不存在單向憎恨關系。
2、由於是圓桌會議，則每個出席的騎士身邊必定剛好有2個騎士。即每個騎士的座位兩邊都必定各有一個騎士。
3、一個騎士無法開會，就是說至少有3個騎士才可能開會。
做法：
1，先對憎惡關系建圖
2，建立上圖的反圖，這時候，圖表明的關系是可以坐在一起。
3，求圖中所有點大於等於3的圈。（tarjan求點雙連通）
4，求3的求出的圈是不是奇圈。（交叉染色法）
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stack>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#define maxn 1001
#define maxm 1000005
vector<int>vc[maxn];
stack<int>st;
vector<int>vec;
int maps[maxn][maxn];
int n,m;
struct list
{
int u;
int e;
int next;
}edge[maxm*2];
int tops,head[maxm*2],vis[maxm*2];
int nums,dnf[maxn],low[maxn],instack[maxn],times;
int mark[maxn],odd[maxn],visit[maxn];;
void add(int x,int y)
{
// printf("%d---%d %d\n",tops,x,y);
edge[tops].u=x;
edge[tops].e=y;
edge[tops].next=head[x];
head[x]=tops++;
}
void init()
{
int a,b,i,j;
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
maps[i][j]=0;
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
maps[a][b]=maps[b][a]=-1;
}
}
void fantu()
{
int i,j;
tops=0;
for(i=0;i<=m*2;i++)head[i]=-1;
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(maps[i][j]==0)
{
add(i,j);
add(j,i);
}
}
int find(int x)
{
int i;
for(i=head[x];i!=-1;i=edge[i].next)
{
int y=edge[i].e;
// cout<<x<<" -- "<<y<<endl;
if(mark[y])
{
if(visit[y]==-1)
{
visit[y]=(visit[x]+1)%2;
if(find(y))return 1;
}
else if(visit[x]==visit[y])return 1;
}
}
return 0;
}
void dos(int x)
{
int i;
memset(visit,-1,sizeof(visit));
visit[x]=0;
if(find(x))
{
for(i=0;i<=n;i++)
if(mark[i])odd[i]=1;
}
}
void tarjan(int x)
{
int i;
low[x]=dnf[x]=times++;
for(i=head[x];i!=-1;i=edge[i].next)
{
if(vis[i])continue;
vis[i]=vis[i^1]=1;
int y=edge[i].e;
// printf("%d-%d----\n",x,y);
if(!dnf[y])
{
st.push(i);
tarjan(y);
low[x]=min(low[x],low[y]);
if(low[y]>=dnf[x])
{
memset(mark,0,sizeof(mark));
int yw=0;
int cc=0;
while(1)
{
cc++;
yw=st.top();
st.pop();
//printf("%d ",yw);
mark[edge[yw].e]=mark[edge[yw].u]=1;
if(edge[yw].u==x)break;
}
// cout<<endl;
if(cc>=3)dos(x);
}
}
else if(dnf[y]<dnf[x])
{
st.push(i);
low[x]=min(low[x],dnf[y]);
}
}
}
void chushihua()
{
int i;
for(i=0;i<=n;i++)low[i]=dnf[i]=instack[i]=0;
for(i=0;i<=n;i++)mark[i]=odd[i]=0;
nums=0;
times=1;
memset(vis,0,sizeof(vis));
while(!st.empty())st.pop();
vec.clear();
}
int sums()
{
int i,s=0;
for(i=1;i<=n;i++)
if(odd[i])s++;
// cout<<" s="<<s<<endl;
return s;
}
int main()
{
//freopen("data.in","r",stdin);
int i;
while(scanf("%d%d",&n,&m)&&(n||m))
{
init();
fantu();
chushihua();
for(i=1;i<=n;i++)
if(!dnf[i])
tarjan(i);
printf("%d\n",n-sums());
}
return 0;
}
