#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 36

int n,m;

int ans=2147483647;

bool B[N][N+1],x[N],path[N];

void Madoka()

{

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

      {

        int j=i;

        for(;j<=n;++j) if(B[j][i]) break;

        if(j!=n+1)

          {

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

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

              if(i!=j&&B[j][i])

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

                  B[j][k]^=B[i][k];

          }

      }

}

void dfs(int cur,int now)

{

    if(now>=ans) return;

    if(!cur) {ans=now; return;}

    if(B[cur][cur])

      {

        bool t=B[cur][n+1];

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

          if(B[cur][i]) t^=path[i];

        path[cur]=t;

        dfs(cur-1,now+t);

      }

    else

      {

        path[cur]=0; dfs(cur-1,now);

        path[cur]=1; dfs(cur-1,now+1);

      }

}

int main()

{

    int x,y;

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

    for(int i=1;i<=n;++i) B[i][n+1]=1,B[i][i]=1;

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

      {

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

        B[x][y]=B[y][x]=1;

      }

    Madoka();

    dfs(n,0);

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

    return 0;

}