#include<cstdio>

#include<algorithm>

using namespace std;

#define N 36

int n;

bool a[N][N];

bool x[N];

int ans=1e9;

void gauss()

{

    int j;

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

    {

        int j=i;

        while(j<n && !a[j][i]) ++j;

        if(j==n) continue;

        swap(a[j],a[i]);

        for(int k=i+;k<n;++k)

            if(a[k][i])

                for(int l=i;l<=n;++l) a[k][l]^=a[i][l];

    }

}

void dfs(int now,int tot)

{

    if(tot>ans) return;

    if(now<) { ans=min(tot,ans); return; }

    if(a[now][now])

    {

        x[now]=a[now][n];

        for(int j=n-;j>now;--j) x[now]^=x[j]&a[now][j];

        if(x[now]) dfs(now-,tot+);

        else dfs(now-,tot);

    }

    else

    {

        x[now]=false;

        dfs(now-,tot);

        x[now]=true;

        dfs(now-,tot+);

    }

}

int main()

{

    int m;

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

    int x,y;

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

    {

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

        x--; y--;

        a[x][y]=a[y][x]=true;

    }

    for(int i=;i<n;++i) a[i][i]=a[i][n]=true;

    gauss();

    dfs(n-,);

    printf("%d",ans);

}