有 $N$ （ $1 \le N \le 35$ ）盏灯，它们的开关通过 $M$ （ $1 \le M \le 595$ ）条连接构成一个网络。 每盏灯都有一个开关，当你切换它时，该灯及所有与之直接相连的灯都会改变状态（开变关，关变开）。 请找出最少需要切换多少次开关，才能把所有灯都打开。 题目保证至少存在一种切换方案可以将所有灯点亮。

在这道题中，以邻接矩阵结合 $n\times 1$ 的全 $1$ 矩阵形成的增广矩阵，可作为异或操作的线性方程组的增广矩阵。对其进行高斯消元，搜索自由元可得到答案。

const int N = 40;

inline ll read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, m;
	int ans;
	bitset<N> a[N];
	void Gauss() {
		for (int i = 1; i <= n; ++i) {
			int cur = i;
			for (; cur <= n && !a[cur].test(i); ++cur);
			if (cur > n) continue;
			if (cur != i) swap(a[cur], a[i]);
			for (int j = i + 1; j <= n; ++j)
				if (a[j].test(i)) a[j] ^= a[i];
		}
	}
	bitset<N> sol;
	void dfs (int x, int sum) {
		if (!x) {
			ans = min(ans, sum);
			return;
		}
		if (sum >= ans) return;
		if (a[x].test(x)) {
			sol[x] = a[x].test(0);
			for (int j = n; j > x; --j) sol.set(x, sol[x] ^ (sol.test(j) & a[x].test(j)));
			dfs (x - 1, sum + sol.test(x));
		} else {
			sol[x] = 0; dfs(x - 1, sum);
			sol[x] = 1; dfs(x - 1, sum + 1);
		}
	}
	int main () {
		n = read(), m = read();
		for (int i = 1; i <= n; ++i) a[i][i] = a[i][0] = 1;
		for (int i = 1; i <= m; ++i) {
			int u = read(), v = read();
			a[u][v] = a[v][u] = 1;
		}
		ans = 1010580540;
		Gauss(); dfs(n, 0);
		printf ("%d\n", ans);
		return 0;
	}
}

int main () {
	string str = "";
//	freopen((str + ".in").c_str(), "r", stdin);
//	freopen((str + ".out").c_str(), "w", stdout);
	Main::main();
	return 0;
}