#include<bits/stdc++.h>
using namespace std;
#define int long long 
int v[40],ans=INT_MAX,t,m,n;
map<int,int> mp;
int dfs(int x,int u,int k,int te)
{
    if(mp[k])
        mp[k]=min(mp[k],te);
    else
        mp[k]=te;
    if(mp[k^t]||k==t)
        ans=min(ans,mp[k^t]+te);
    if(x<=u)
    {
        dfs(x+1,u,k,te);
        k=k^v[x];
        dfs(x+1,u,k,te+1);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        v[a]=v[a]^1<<b;
        v[b]=v[b]^1<<a;
    }
    for(int i=1;i<=n;i++)
    {
        t=t^1<<i;
        v[i]=v[i]^1<<i;
    }
    dfs(1,n/2,0,0);
    dfs(n/2+1,n,0,0);
    cout<<ans<<endl;
    return 0;
}