# include <bits/stdc++.h>
# define R register
# define db double
# define mi 1e-8

using namespace std;

int n,m,x,y,ans=10000,l[110];
int a[110][110];

template <typename T> inline void in(R T& a){
    R char c=getchar(); R T x=0,f=1;
    while(!isdigit(c)) {if(c == '-') f=-1; c=getchar();}
    while(isdigit(c)) x=(x<<1)+(x<<3)+c-'0',c=getchar();
    a=x*f;
}

template <typename T> inline T ab(R T& a){return a<0? -a:a;}

inline bool gauss(){//高斯消元
    R bool flagg=1;
    for(R int i=1; i<=n; ++i)
    {
        R int k=i;
        while(k<=n&&!a[k][i]) k++;
        if(k>n) {flagg=0; continue;}
        swap(a[i],a[k]);
        for(R int j=1; j<=n; ++j)
        {
            if(i==j||!a[j][i]) continue;
            for(R int k=i+1; k<=n+1; ++k) a[j][k]^=a[i][k];
            a[j][i] = 0;
        }
    }
    return flagg;
}

inline void dfs(R int x,R int num){
    // printf("%d ",x);
    if(num>=ans) return;//剪枝
    if(x == n+1){ans = num; return;}
    if(a[x][x])//不是自由元
    {
        R bool v=a[x][n+1];
        for(R int i=x-1; i>=1; --i) if(a[x][i]) v^=l[i];
        dfs(x+1,num+v);
    }
    else{
        dfs(x+1,num);
        l[x]=1;
        dfs(x+1,num+1);
        l[x]=0;
    }
}

int main(){
    // freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);
    in(n),in(m);
    for(R int i=1; i<=n; ++i) a[i][i] = a[i][n+1] = 1;
    for(R int i=1; i<=m; ++i) in(x),in(y),a[x][y] = a[y][x] = 1;
    if(gauss()){
        R int ans = 0;
        for(R int i=1; i<=n; ++i) ans += a[i][n+1];
        printf("%d",ans);
    }
    else dfs(1,0),printf("%d\n",ans);
    return 0;
}