#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x << ": " << (x) << endl
#else
#define debug(x)
#endif
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int maxn=1<<20,inf=0x3f3f3f3f,mod=1e9+7;

int f[maxn],cnt[maxn],pop[maxn];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=0,u,v;i<m;++i)
    {
        cin>>u>>v;
        u--;
        v--;
        for(int j=0;j<(1<<n);++j) if(j&(1<<u) && (j&(1<<v))) cnt[j]++;
    }
    for(int i=1;i<(1<<n);++i) pop[i]=pop[i>>1]+(i&1);
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=0;i<(1<<n);++i)
    {
        int c=pop[i];
        for(int j=i;j;j=(j-1)&i)
        {
            if(pop[j]*(pop[j]-1)/2==cnt[j]) f[i]=min(f[i],f[i^j]+1);
        }
    }
    cout<<f[(1<<n)-1]<<'\n';
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

template <class A, class B> bool cmin(A& a, B b) { return a > b && (a = b, true); }
template <class A, class B> bool cmax(A& a, B b) { return a < b && (a = b, true); }

class ChromaticrNumber {
public:
  int V;
  vector<int> adj;
  const static int MOD = 1000000007;
  ChromaticrNumber(int node_size) : V(node_size), adj(V, 0) {
    for (int i = 0; i < V; i++) {
      adj.at(i) = (1 << i);
    }
  }
  void add(int u, int v) {
    adj.at(u) |= (1 << v), adj.at(v) |= (1 << u);
  }
  int solve() {
    vector<int> t(1 << V, 0), I(1 << V, 0);
    t.at((1 << V) - 1) = I.at(0) = 1;
    for (int i = 1; i < (1 << V); i++) {
      int v = __builtin_ctz(i);
      I.at(i) = I.at(i ^ (1 << v)) + I.at(i & (~adj.at(v)));
      I.at(i) = (I.at(i) >= MOD) ? (I.at(i) - MOD) : I.at(i);
      t.at(i - 1) = (((V - __builtin_popcount(i - 1)) % 2) ? (MOD - 1) : 1);
    }
    for (int k = 1; k < V; k++) {
      long res = 0;
      for (int i = 0; i < (1 << V); i++) {
        res += (t.at(i) = (long) t.at(i) * I.at(i) % MOD);
      }
      if (res % MOD) return k;
    }
    return V;
  }
};

signed main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int N, M;
  cin >> N >> M;
  vector<pair<int, int>> V(M);
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b, a--, b--;
    if (a > b) swap(a, b);
    V.at(i) = {a, b};
  }

  set<pair<int, int>> SE;
  for (const auto& [a, b] : V) SE.insert({a, b});

  ChromaticrNumber CN(N);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < i; j++) {
      if (SE.count({j, i})) continue;
      CN.add(j, i);
    }
  }
  cout << CN.solve() << '\n';
}