#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<map>
#include<cstring>
using namespace std;
int a[100][100];
const int N=1e6;
int L[N],dp[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        a[x][y]=1;
        a[y][x]=1;
    }
    int R=1<<n;
    for(int S=0;S<R;S++){
        int flag=1;
        for(int i=1;i<=n;i++){
            int x1=i-1;
            if(!((S>>x1)&1)) continue;
            for(int j=i+1;j<=n;j++){
                int x2=j-1;
                if(!((S>>x2)&1)) continue;
                if(a[i][j]==0){
                    flag=0;
                    break;
                }
            }
            if(flag==0) break;
        }
        L[S]=flag;
    }
    for(int S=1;S<R;S++){
        dp[S]=n+1;
        for(int T=S;T;T=(T-1)&S){
            if(L[T]) dp[S]=min(dp[S],dp[T^S]+1);
        }
    }
    printf("%d\n",dp[R-1]);
}
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define REP(i,n) for (int i = 1; i < (int)(n); i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define debug(var) do{cout << #var << " : "; view(var);}while(0)
template<class T> bool chmin(T &a, T b) {if(a>b) {a=b;return 1;}return 0;}
template<class T> bool chmax(T &a, T b) {if(a<b) {a=b;return 1;}return 0;}
using namespace std;
template<class T> void view(T e) {cout << e << endl;}
template<class T> void view(const vector<T> &v) {for(const auto &e : v){cout << e << " ";} cout << endl;}
template<class T> void view(const vector<vector<T>> &vv) {for(const auto &v : vv){view(v);}}
using vint = vector<int>;
using vvint = vector<vector<int>>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<int,int>;
const int inf = 1<<30;
const ll inf_l = 1LL<<61;
const int MAX = 1e5;

int main() {
    int n, m; cin >> n >> m;
    vint g(n, 0);
    rep(i,n) g[i] |= 1 << i;
    rep(i,m) {
        int a, b; cin >> a >> b;
        a--; b--;
        g[a] |= 1 << b;
        g[b] |= 1 << a;
    }
    vector<bool> connect(1 << n, false);
    connect[0] = true;
    rep(i,1<<n) {
        if (connect[i]) {
            rep(j,n) {
                if ((i & g[j]) == i) connect[i | (1 << j)] = true;
            }
        }
    }
    vint dp(1 << n, inf);
    for (int i = 1; i < 1 << n; i++) {
        if (connect[i]) dp[i] = 1;
        else {
            for (int j = i; j > 0; --j &= i) {
                if (j == i) continue;
                chmin(dp[i], dp[j] + dp[i ^ j]);
            }
        }
    }
    cout << dp.back() << endl;
}