#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <bitset>

using namespace std;

const int N=,INF=1e9;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,m,u,v;

bitset<N> a[N];

int fe[N],now,pivot[N];

void Gauss(){

    now=;

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

        int j=now;//printf("hi %d %d    %d\n",i,now,a[now][i]==1);

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

        if(j==n+) {fe[++fe[]]=i;continue;}

        if(j!=now) swap(a[now],a[j]);

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

            if(j!=now&&a[j][i]) a[j]^=a[now];

        pivot[i]=now;//printf("pivot %d\n",i);

        now++;

    }

}

int val[N],tot,ans=INF;

void pri(){

    puts("free");

    for(int i=;i<=fe[];i++) printf("fe %d %d %d\n",i,fe[i],val[i]);

    puts("end");

}

int fir=;

void dfs(int d){

    //printf("dfs %d %d\n",d,tot);

    if(tot>=ans) return;

    if(d==) ans=min(ans,tot);//if(fir==1) printf("tot %d\n",tot),pri(),fir=0;}

    else if(pivot[d]){//printf("d %d\n",d);

        int i=pivot[d];

        int _=a[i][n+];

        for(int j=;j<=fe[];j++)

            if(a[i][fe[j]]) _^=val[fe[j]];

        tot+=_;

        dfs(d-);

        tot-=_;

    }else{

        val[d]=;

        dfs(d-);

        val[d]=; tot++;

        dfs(d-);

        tot--;

    }

}

int main(){

    //freopen("in","r",stdin);

    n=read();m=read();

    for(int i=;i<=m;i++) u=read(),v=read(),a[u][v]=a[v][u]=;

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

    Gauss();

    //for(int i=1;i<=n;i++) printf("a %d %d\n",i,a[i][n+1]==1);

    //for(int i=1;i<=fe[0];i++) printf("fe %d %d\n",i,fe[i]);

    dfs(n);

    printf("%d",ans);

}