记录编号	451403	评测结果	AAAAAAAAAAAAAAAAA
题目名称	牛棚的灯	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2017-09-17 16:42:13	内存使用	0.32 MiB

#include <cstdio>
#include <iostream>
#include <cstring>
#define maxn 40
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
inline int read()
{   char c=getchar();int x=0,y=1;
    while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*y;
}
template<typename T>
inline T m_min(T x,T y){return x<y?x:y;}
int n,m,A[maxn][maxn],ans[maxn],cnt,fans=0x7fffffff;
inline void dfs(int x)
{	if(cnt>=fans) return;
	if(!x){fans=m_min(fans,cnt);return;}
	if(A[x][x])
	{	bool now=A[x][n+1];
		for(int i=x+1;i<=n;++i)
			if(A[x][i]) now^=ans[i];
		ans[x]=now;
		if(now) ++cnt;
		dfs(x-1);
		if(now) --cnt;
	}
	else
	{	++cnt;ans[x]=1;dfs(x-1);
		--cnt;ans[x]=0;dfs(x-1);
	}
}
void gs()
{	for(int i=1;i<=n;++i)
	{	int tmp=i;
		while(tmp<=n&&!A[tmp][i]) ++tmp;
		if(tmp>n) continue;
		if(i!=tmp) for(int k=1,edg=n+1;k<=edg;++k) swap(A[i][k],A[tmp][k]);
		for(int j=1;j<=n;++j)
			if(i!=j&&A[j][i])
				for(int k=1,edg=n+1;k<=edg;++k) A[j][k]^=A[i][k];
	}
}
int main()
{	freopen("lights.in","r",stdin);
	freopen("lights.out","w",stdout);
	n=read();m=read();int x,y;
	for(int i=1;i<=n;++i) A[i][i]=A[i][n+1]=1;
	for(int i=1;i<=m;++i)
		x=read(),y=read(),A[x][y]=1,A[y][x]=1;
	gs();dfs(n);
	printf("%d",fans);
}