记录编号	380435	评测结果	AAAAAAAAAA
题目名称	[HAOI 2013]开关控制	最终得分	100
用户昵称	Mealy	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2017-03-09 12:55:58	内存使用	0.29 MiB

//1371
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int nmax=40;
const int INF=0x3f3f3f3f;
int N,M;
int G[nmax][nmax]={0};
int x[nmax]={0};
int u,v;
int ans;
void PreDo(){
	ans=INF;
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;i++){
		scanf("%d%d",&u,&v);
		G[u][v]=1;
		G[v][u]=1;
	}
	for(int i=1;i<=N;i++){
		G[i][N+1]=1;
		G[i][i]=1;
	}
//	printf("aaaa\n");
}

void DFS(int now,int t){
	if(t>ans){
		return;
	}
	if(now==0){
		ans=min(ans,t);
		/*
		for(int i=1;i<=N;i++){
			printf("%d ",x[i]);
		}
		printf("\n");*/
		return;
	}
	if(G[now][now]){
		int tmp=G[now][N+1];
		for(int i=now+1;i<=N;i++){
			if(G[now][i]){
				tmp^=x[i];
			}
		}
		x[now]=tmp;
		DFS(now-1,t+x[now]);
	}
	else{
//		printf("aaaaaaaaaaaaaaaaaaaaa\n");
		x[now]=1;
		DFS(now-1,t+1);
		x[now]=0;
		DFS(now-1,t);
	}
	return;
}
	
void Swap(int* a,int* b){
	int tmp; 
	for(int i=1;i<=N+1;i++){
		tmp=a[i];
		a[i]=b[i];
		b[i]=tmp;
	}
	return;
}		
void Disappear(){
//	printf("%d\n",N);
	for(int i=1;i<=N;i++){
		for(int j=i;j<=N;j++){
			if(G[j][i]==1){
				Swap(G[i],G[j]);
				break;
			}
		}
		for(int j=i+1;j<=N;j++){
			if(!G[j][i]){
				continue;				
			}
			for(int k=i;k<=N+1;k++){
				G[j][k]^=G[i][k];
//				G[j][k]^=1;
			}
		}	
	}/*
	for(int i=1;i<=N;i++){
		for(int j=1;j<=N+1;j++){
			printf("%d ",G[i][j]);
		}
		printf("\n");
	}*/
}
int main(){
	freopen("haoi13t3.in","r",stdin);
	freopen("haoi13t3.out","w",stdout);
	PreDo();
	Disappear();
//	printf("aaaa\n");
	DFS(N,0);
	printf("%d\n",ans);
	return 0;
}