/**************************************************************

    Problem: 1770

    User: BeiYu

    Language: C++

    Result: Accepted

    Time:416 ms

    Memory:5384 kb

****************************************************************/

#include <cstdio>

#include <map>

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 40;

int n,m,ans=N;

LL state,pow2[N],a[N];

map< LL,int > mp;

void DFS1(int l,int r,int w,LL s){

    if(l>r){ if(mp.find(s)==mp.end() || mp[s]>w) mp[s]=w;return; }

    DFS1(l+1,r,w,s);

    DFS1(l+1,r,w+1,s^a[l]);

}

void DFS2(int l,int r,int w,LL s){

    if(l>r){ if(mp.find(state^s)!=mp.end()) ans=min(ans,w+mp[state^s]);return; }

    DFS2(l+1,r,w,s);

    DFS2(l+1,r,w+1,s^a[l]);

}

int main(){

    cin>>n>>m;

    pow2[0]=1LL;

    for(int i=1;i<=n;i++) pow2[i]=pow2[i-1]<<1;

    for(int i=0;i<n;i++) a[i]|=pow2[i],state|=pow2[i];

    for(int i=1,u,v;i<=m;i++){

        cin>>u>>v;

        u--,v--;

        a[u]|=pow2[v],a[v]|=pow2[u];

    }

    DFS1(0,min(n-1,n/2),0,0);

    DFS2(min(n-1,n/2)+1,n-1,0,0);

    cout<<ans<<endl;

    return 0;

}