#include <cmath>

#include <cstdio>

#include <iostream>

#define N 40

using namespace std;

int n, m, sum, mn = ~(1 << 31);

int a[N][N], ans[N];

inline void Guass()

{

	int i, j, k;

	for(j = 1; j <= n; j++)

	{

		k = j;

		for(i = j; i <= n; i++)

			if(a[i][j] > a[k][j])

				k = i;

		if(k != j) swap(a[k], a[j]);

		for(i = j + 1; i <= n; i++)

			if(a[i][j])

				for(k = j; k <= n + 1; k++)

					a[i][k] ^= a[j][k];

	}

}

inline void dfs(int now, int sum)

{

	if(sum >= mn) return;

	if(!now)

	{

		mn = min(mn, sum);

		return;

	}

	int i;

	if(a[now][now])

	{

		ans[now] = a[now][n + 1];

		for(i = now + 1; i <= n; i++)

			ans[now] ^= (ans[i] * a[now][i]);

		dfs(now - 1, sum + bool(ans[now]));

	}

	else

	{

		ans[now] = 0;

		dfs(now - 1, sum);

		ans[now] = 1;

		dfs(now - 1, sum + 1);

	}

}

int main()

{

	int i, x, y;

	scanf("%d %d", &n, &m);

	for(i = 1; i <= n; i++) a[i][i] = 1, a[i][n + 1] = 1;

	for(i = 1; i <= m; i++)

	{

		scanf("%d %d", &x, &y);

		a[x][y] = 1;

		a[y][x] = 1;

	}

	Guass();

	dfs(n, 0);

	printf("%d\n", mn);

	return 0;

}