http://acm.hdu.edu.cn/showproblem.php?pid=5727
题意：n个珠子，每个珠子有阴阳两种属性，且阴的一定和阳的紧邻，排成一个环；m行，每行两个数，表示阳性x珠子和y阴性珠子相邻则功能减弱，问功能减弱珠子最少有几个
思路：二分匹配
全排列阴性珠子，因为是环，O((n-1)!)；枚举每个阳性珠子，插入i位置，前提是i前后两个阴性珠子都不与阳性珠子有排斥作用；
最后问题变转化成，阳性珠子和位置的最大匹配问题
// #pragma comment(linker, "/STACK:102c000000,102c000000")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdlib>
// #include <conio.h>
using namespace std;
#define clc(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N = ;
const int M = 1e6+;
const int MOD = 1e9+;
#define LL long long
#define LB long double
#define mi() (l+r)>>1
double const pi = acos(-);
const double eps = 1e-;
void fre() {
freopen("in.txt","r",stdin);
}
// inline int r() {
// int x=0,f=1;char ch=getchar();
// while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}
// while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;
// }
int mp[][];
int a[];
int n,m;
int ans;
bool vis[];
int b[];
vector<int>s[];
bool dfs(int x){
if(vis[x]) return false;
vis[x]=;
for(int i=;i<(int)s[x].size();i++){
int v=s[x][i];
if(b[v]==-||dfs(b[v])){
b[v]=x;
return true;
}
}
return false;
} void hungarian(){
clc(b,-);
int tem=;
for(int i=;i<=n;i++){
clc(vis,);
if(dfs(i))
tem++;
}
if(tem>ans) ans=tem;
}
void work(){
for(int i=;i<n;i++){
a[i]=i+;
}
do{
for(int i=;i<=;i++) s[i].clear();
for(int i=;i<n;i++){
int k1=a[i],k2=a[(i-+n)%n];
for(int j=;j<=n;j++){
if(!mp[k1][j]&&!mp[k2][j]) s[j].push_back(i);
}
}
hungarian();
}while(next_permutation(a+,a+n)&&ans!=n);
}
int main(){
// fre();
while(~scanf("%d%d",&n,&m)){
clc(mp,);
ans=;
for(int i=;i<m;i++){
int x,y;
scanf("%d%d",&x,&y);
mp[y][x]=;
}
work();
printf("%d\n",n-ans);
}
return ;
}