#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

signed main() {
    int n, m;
    cin >> n >> m;
    int a[m], b[m];
    rep(i, m) {
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
    }
    int dp[1 << n] = {};
    fill(dp, dp + (1 << n), INF);
    for (int bit = 1; bit < 1 << n; bit++) {
        int bp = __builtin_popcount(bit);
        int cnt = 0;
        rep(i, m) {
            if ((bit & 1 << a[i]) and (bit & 1 << b[i])) cnt++;
        }
        if (cnt == bp * (bp - 1) / 2) dp[bit] = 1;
    }
    for (int S = 0; S < 1 << n; S++) {
        for (int T = S;; T = (T - 1) & S) {
            if (T == 0) break;
            dp[S] = min(dp[S], dp[T] + dp[S ^ T]);
        }
    }
    cout << dp[(1 << n) - 1] << endl;
    return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1<<18,INF=-0x3f3f3f3f3f;
int N,F[MAXN],G[MAXN],U,Con[MAXN],IsCon[MAXN];
inline int lowbit(int n) { return n&(-n); }
inline bool iscon(int b,int s){
    if(G[s]!=1) return 0;
    while(s){
        if(!Con[b|lowbit(s)]) return 0;
        s^=lowbit(s);
    }
    return 1;
}
vector<int> Alw;
inline void dp(int S){
    if( S==lowbit(S)||iscon(lowbit(S),S^lowbit(S)) ){
        F[S]=G[S]=1;
        Alw.push_back(S);
        return ;
    }
    for(auto s : Alw)
        if((S&s)==s){
            F[S]=min(F[S],F[S^s]+1);
            if(F[S]==2) return ;
        }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    for(int i=0;i<MAXN;i++) F[i]=G[i]=-INF;
    int M;
    cin>>N>>M;
    U=(1<<N)-1;
    for(int i=1;i<=M;i++){
        int a,b;
        cin>>a>>b;
        Con[(1<<a-1)|(1<<b-1)]=1;
    }
    for(int i=1;i<=U;i++) dp(i);
    cout<<F[U]<<endl;
    return 0;
}