记录编号	386627	评测结果	AAAAAAAAAA
题目名称	[HAOI 2013]开关控制	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2017-03-24 20:29:54	内存使用	0.33 MiB

/*kZime*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <algorithm>
#define MAXN 64
using namespace std;
inline int read() {
	int k = 0, f = 1; char c = getchar();
	for(; !isdigit(c); c = getchar())if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}
/*-----------------------------------------------------------------------------*/
int a[MAXN][MAXN], n, m, ans = 1e9;
bool free_yuan[MAXN], slt[MAXN];

void dfs(int now, int tmp) {
	if(tmp > ans) return;
	if(now <= 0) {
		ans = min(ans, tmp);
		return;
	}
	if(free_yuan[now]) {
		slt[now] = 1;
		dfs(now - 1, tmp + 1);
		slt[now] = 0;
		dfs(now - 1, tmp);
	}
	else {
		slt[now] = a[now][0];
		for(int i = now + 1; i <= n; i++) {
			if (a[now][i]) slt[now] ^= slt[i];
		}
		dfs(now - 1, tmp + slt[now]);
	}
}

int main() {
#ifndef MYLAB
	freopen("haoi13t3.in", "r", stdin);
	freopen("haoi13t3.out", "w", stdout);
#else
	freopen("in.txt", "r", stdin);
#endif

	n = read();
	m = read();
	for(int i = 1; i <= n; i++) a[i][i] = 1, a[i][0] = 1;
	for(int i = 1; i <= m; i++) {
		int u = read();
		int v = read();
		a[u][v] = 1;
		a[v][u] = 1;
	}
	
	for(int i = 1; i <= n; i++) {
		free_yuan[i] = 1;
		for(int j = i; j <= n; j++) {
			if(!a[j][i]) continue;
			for(int k = i; k <= n; k++) {
				swap(a[i][k], a[j][k]);
			}
			swap(a[i][0], a[j][0]);
			break;
		}
		if(!a[i][i]) continue;
		else {
			free_yuan[i] = 0;
			for (int j = i + 1; j <= n; j++) {
				if (!a[j][i]) continue;
				for (int k = i; k <= n; k++) a[j][k] ^= a[i][k];
				a[j][0] ^= a[i][0];
			}
		}
	}

	dfs(n, 0);
	printf("%d", ans);

	return 0;
}