# hdu5727

给你最n个阳珠子和n个阴珠子（n≤9），要你串成阴阳相隔的珠链,有一些阳珠子不能和某些阴珠子放一起,否则会失去光芒,询问至少有几个阳珠子失去光芒.

1.考虑旋转，锁定全排列中第一个数字即可
2.考虑翻转，hash环排列以及他的翻转排列即可
```#include<bits/stdc++.h>
using namespace std;

const double eps=1e-12;
struct dinic{
static const int maxn=30;
static const int maxm=900;
static const int inf=1e9;
struct edge{
int v,nex;
double c;
} g[2*maxm];

//cout<<u<<" "<<v<<endl;
g[cnt].v=v;
g[cnt].c=c;

g[cnt].v=u;
g[cnt].c=0;
}

void ini(){
cnt=0;
}

void bfs(int s){
memset(lv,-1,sizeof(lv));
lv[s]=0;
queue<int>q;
q.push(s);
while(!q.empty()){
int u=q.front();q.pop();
edge&e=g[i];
//if(e.c<=0||lv[e.v]>=0)continue;
if(e.c<2*eps||lv[e.v]>=0)continue;
lv[e.v]=lv[u]+1;
q.push(e.v);
}
}
}

double dfs(int u,int t,double f){
if(u==t)return f;
for(int&i=current[u]; ~i; i=g[i].nex){
edge&e=g[i],&rev=g[i^1];
//if(e.c<=0||lv[u]>=lv[e.v])continue;
if(e.c<eps||lv[u]>=lv[e.v])continue;
double d=dfs(e.v,t,min(f,e.c));
//if(d<=0)continue;
if(d<eps)continue;
e.c -=d;
rev.c+=d;
return d;
}
return 0;
}

double maxflow(int s,int t){
double flow=0;
while(true){
bfs(s);
if(lv[t]<0)return flow;
double f;
//while((f=dfs(s,t,inf))>0)flow+=f;
while((f=dfs(s,t,inf))>eps)flow+=f;//注意括号
}
}
} g;

bool limit[20][20];
int a[20];

int gethash(int*a,int n){// [1,n]
int ret=a[1];
for(int i=2;i<=n;i++){
ret*=10;
ret+=a[i];
}
return ret;
}
int gethashrev(int*a,int n){// [1,n]
int ret=a[1];
for(int i=n;i>=2;i--){
ret*=10;
ret+=a[i];
}
return ret;
}

map<int,bool>mp;

int solve(int *a,int n){
g.ini();
int s=2*n+1;
int t=2*n+2;

for(int i=1;i<=n;i++){

for(int j=1;j<=n;j++){
if((!limit[a[i]][j])&&(!limit[a[i+1]][j])){
}
}
}

return g.maxflow(s,t)+0.5;
}

int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
if(n==0){
cout<<0<<endl;
continue;
}
//init
for(int i=1;i<=n;i++)a[i]=i;
a[n+1]=1; //a[i]..a[i+1]   1<=i<=n
memset(limit,0,sizeof(limit));
mp.clear();

while(m--){
int u,v;
scanf("%d%d",&u,&v);
limit[v][u]=true;
}

int ans=1000;

do{
int hash=gethash(a,n);
if(mp[hash]==true)continue;
mp[hash]=true;
mp[gethashrev(a,n)]=true;
ans=min(ans,n-solve(a,n));

}while(next_permutation(a+2,a+1+n));

cout<<ans<<endl;
}
}
```