#include<map>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long LL;

LL Bin[];

int cnt,mn;

LL p[],ed;//状压，p[i]代表假如我按i，会对那些造成影响就在相应位上记为1

bool half;

map<LL,int>f;

void dfs(int x,LL now,int d)

{

    if(x==cnt+)

    {

        if(now==ed)mn=min(mn,d);//到达

        else

        {

            if(half==false)//第一次，记录到达该状态的最优方案

            {

                int c=f[now];

                if(c==||c>d)f[now]=d;

            }

            else //第二次，看看我和其他合并能否到达最终状态

            {

                int c=f[ed-now];

                if(c!=)mn=min(mn,c+d);

            }

        }

        return ;

    }

    dfs(x+,now,d);//穷举状态

    dfs(x+,now^p[x],d+);

}

int main()

{

    int n,m,x,y;

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

    p[]=Bin[]=;for(int i=;i<=n+;i++)p[i]=Bin[i]=Bin[i-]*;

    ed=Bin[n+]-;//结束状态就是全为1 

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

    {

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

        p[x]+=Bin[y];p[y]+=Bin[x];//记录所影响的

    }

    mn=;

    half=false;cnt=n/;dfs(,,);//折半搜索

    half=true;cnt=n;dfs(n/+,,);

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

    return ;

}