#include<bits/stdc++.h>
using namespace std;
#define int long long
map<int,int> mp;
const int maxn = 50;
int a[maxn];
signed main()
{
    mp[0] = 0;
	int n,m;
	cin >> n >> m;
	if(n == 0)
	{
	    cout << 0 << endl;
	    return 0;
	}
	int ans = 0x3f3f3f3f3f3f3f3f;
	a[0] = 1;
	for(int i = 1;i < n;i++)
	{
		a[i] = a[i - 1] << 1;
	}
	
	for(int i = 1;i <= m;i++)
	{
		int u,v;
		cin >> u >> v;
		u--;
		v--;
		a[u] |= (1ll << v);
		a[v] |= (1ll << u);
	}
	
	for(int i = 0;i < 1ll << (n >> 1);i++)
	{
		int t = 0;
		int cnt = 0;
		for(int j = 0;j < (n >> 1);j++)
		{
			if((i >> j) & 1)
			{
				t ^= a[j];
				cnt++;
			}
		}
		if(!mp.count(t))
		{
			mp[t] = cnt;
		}
		else
		{
			mp[t] = min(mp[t],cnt);
		}
	}
	int u = (1ll << n) - 1;
	for(int i = 0;i < 1ll << (n - (n >> 1));i++)
	{
		int t = 0;
		int cnt = 0;
		for(int j = 0;j < (n - (n >> 1));j++)
		{
			if((i >> j) & 1)
			{
				t ^= a[(n >> 1) + j];
				cnt++;
			}
		}
		if(mp[u ^ t]) ans = min(ans,mp[u ^ t] + cnt);	
	}
	cout << ans << endl;
	return 0;
	
}