
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
typedef long long ll;

int n;
int g[21];
bool isOK(int pat) {
  REP(i, n) {
    if(pat & (1 << i)) {
      if((g[i] & pat) != pat) {
        return false;
      }
    }
  }
  return true;
}
  
int memo[1 << 18];

int solve(int rest) {
  int &res = memo[rest];
  if(res < 0) {
    if(rest == 0) {
      res = 0;
    } else if(((rest-1) & rest) == 0) {
      res = 1;
    } else {
      int first = rest & -rest;
      int rest2 = rest ^ first;
      res = 1 + solve(rest2);
      for(int s = rest2; s; s = (s-1) & rest2) {
        if(isOK(s | first)) {
          res = min(res, 1 + solve(rest ^ first ^ s));
        }
      }
    }
  }
  return res;
}

int main(void) {
  int nEdge;
  scanf("%d%d", &n, &nEdge);
  REP(i, n) {
    g[i] |= 1 << i;
  }
  REP(i, nEdge) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a;
    --b;
    g[a] |= 1 << b;
    g[b] |= 1 << a;
  }
  if(nEdge == n*(n-1) / 2) {
    cout << 1 << endl;
    return 0;
  }
  memset(memo, -1, sizeof memo);
  int res = solve((1 << n)-1);
  cout << res << endl;
  
  return 0;
}

#include <bits/stdc++.h>
#include <vector>
#include<math.h>
#include<string.h>
using namespace std;
#define MAX 6000005
#define MOD 1000000007
#define SMOD 998244353
#define GMAX 19
#define INF 2000000000000000000
#define EPS 0.0000000001
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL)
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
int n;
int Graph[GMAX];
bool possibility[MAX];
int components[MAX];
int mcom(int mask)
{
    if(components[mask]!=-1)
    {
        return components[mask];
    }
    components[mask]=n;
    int i;
    for(i=mask;i>0;i=mask&(i-1))
    {
        if(possibility[i]) components[mask]=min(components[mask],1+mcom(mask^i));
    }
    return components[mask];
}
int main()
{
    int i,m,j;
    scanf("%d %d",&n,&m);
    for(i=0;i<n;i++)
    {
        int mask=1<<i;
        Graph[i]=Graph[i]|mask;
    }
    for(i=0;i<m;i++)
    {
        int u,v;
        scanf("%d %d",&u,&v);
        u--;
        v--;
        int U=1<<u;
        int V=1<<v;
        Graph[u]=Graph[u]|V;
        Graph[v]=Graph[v]|U;
    }
    m=1<<n;
    for(i=0;i<m;i++)
    {
        int mask=i;
        for(j=0;j<n;j++)
        {
            int tmask=1<<j;
            tmask=tmask&mask;
            if(tmask==0) continue;
            tmask=mask;
            tmask=tmask&Graph[j];
            if(tmask!=mask) break;
        }
        possibility[i]=(j>=n);
        components[i]=-1;
    }
    components[0]=0;
    j=mcom(m-1);
    printf("%d",j);
    return 0;
}
