貝希和她的閨密們在她們的牛棚中玩遊戲。但是天不從人願，突然，牛棚的電源跳閘了，所有的燈都被關閉了。貝希是一個很膽小的女生，在伸手不見拇指的無盡的黑暗中，她感到驚恐，痛苦與絕望。她希望您能夠幫幫她，把所有的燈都給重新開起來！她才能繼續快樂地跟她的閨密們繼續玩遊戲！ 牛棚中一共有N（1 <= N <= 35）盞燈，編號為1到N。這些燈被置於一個非常複雜的網絡之中。有M（1 <= M <= 595）條很神奇的無向邊，每條邊連接兩盞燈。 每盞燈上面都帶有一個開關。當按下某一盞燈的開關的時候，這盞燈本身，還有所有有邊連向這盞燈的燈的狀態都會被改變。狀態改變指的是：當一盞燈是開著的時候，這盞燈被關掉；當一盞燈是關著的時候，這盞燈被打開。 問最少要按下多少個開關，才能把所有的燈都給重新打開。 數據保證至少有一種按開關的方案，使得所有的燈都被重新打開。

＊第一行：兩個空格隔開的整數：N和M。

＊第二到第M+1行：每一行有兩個由空格隔開的整數，表示兩盞燈被一條無向邊連接在一起。 沒有一條邊會出現兩次。

第一行：一個單獨的整數，表示要把所有的燈都打開時，最少需要按下的開關的數目。

Gold

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>//by NeighThornusing namespace std;const int maxn=35+5;int n,m,ans,a[maxn][maxn],tmp[maxn];inline void gauss(void){	for(int i=1;i<=n;i++){		int k=i;		while(!a[k][i]&&k<=n)			k++;		if(a[k][i]){			if(k!=i)				for(int s=1;s<=n+1;s++)					swap(a[k][s],a[i][s]);			for(int l=1;l<=n;l++)				if(l!=i&&a[l][i])					for(int s=1;s<=n+1;s++)						a[l][s]^=a[i][s];		}	}}inline void dfs(int id,int cnt){	if(cnt>=ans)		return;	if(id==0){		ans=min(ans,cnt);		return;	}	if(a[id][id]){		tmp[id]=a[id][n+1];		for(int i=n;i>id;i--)			if(a[id][i])				tmp[id]^=tmp[i];		dfs(id-1,cnt+tmp[id]);	}	else			tmp[id]=0,dfs(id-1,cnt),		tmp[id]=1,dfs(id-1,cnt+1);}signed main(void){	scanf("%d%d",&n,&m);	for(int i=1;i<=n;i++)		a[i][i]=a[i][n+1]=1;	for(int i=1,x,y;i<=m;i++)		scanf("%d%d",&x,&y),a[x][y]=a[y][x]=1;	ans=n+1;gauss();dfs(n,0);printf("%d\n",ans);	return 0;}