#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
#define ll long long
#define rep(i,n) for (int i=0;i<(n);i++)
#define N 2222

int ef[N],es[N],first[N],next[N],c,n,m,ans=N,l;
map<ll,int> t1,t2;

void add(int x,int y){
    next[++c]=first[x];first[x]=c;
    ef[c]=x;es[c]=y;
    next[++c]=first[y];first[y]=c;
    ef[c]=y;es[c]=x;
}

void init(){
    freopen("lights.in","r",stdin);
    freopen("lights.out","w",stdout);
    scanf("%d%d",&n,&m);
    rep(i,m){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
    }
}

int main(){
    init();
    m=n/2,l=n-m;
    rep(i,1<<m){
        ll cur=0;int ff=0;
        rep(j,m) if (i & (1<<j)){
            cur^=(1ll<<j);++ff;
            for (int h=first[j+1];h;h=next[h]) cur^=(1ll<<(es[h]-1));
        }
        if (t1.count(cur)) t1[cur]=min(t1[cur],ff);
        else t1[cur]=ff;
    }
    rep(i,1<<l){
        ll cur=0;int ff=0;
        rep(j,l) if (i & (1<<j)){
            cur^=(1ll<<(j+m));++ff;
            for (int h=first[j+m+1];h;h=next[h]) cur^=(1ll<<(es[h]-1));
        }
        if (t2.count(cur)) t2[cur]=min(t2[cur],ff);
        else t2[cur]=ff;
    }
    ll finish=(1ll<<n)-1;
    if (t1.count(finish)) ans=t1[finish];
    if (t2.count(finish)) ans=min(ans,t2[finish]);
    for (map<ll,int>::iterator it=t1.begin();it!=t1.end();it++){
        ll ff=it->first ^ finish;
        if (t2.count(ff)) ans=min(ans,it->second+t2[ff]);
    }
    printf("%d\n",ans);
    return 0;
}