// --------------------------------------------------<C++ TEMPLATE>------------------------------------------------
/**
    *  Nitin Gangwar
    *  @wargang (codechef,codeforces,spoj,gfg)
    *  MNNIT allahabad
    *  CSE'23
    *  iamnitingangwar2000@gmail.com
**/

#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// MACROS
#define int                     long long
#define mp                      make_pair
#define pb                      push_back
#define MAX                     1e17
#define MIN                     -1e17
#define PI                      3.1415926535897932384626433832795
#define mod                     1000000007
#define set(x)                  memset(x, 0, sizeof(x))
#define clr(x)                  memset(x, -1, sizeof(x))
#define ff                      first
#define ss                      second
#define rep(i,n)                for(int i=0;i<(n);i++)
#define FOR(i,a,b)              for(int i=(a);i<=(b);i++)
#define FORD(i,a,b)             for(int i=(a);i>=(b);i--)
#define sz(x)                   x.size()
#define endl                    "\n"
#define deb(x)                  cout << #x << "=" << x << endl
#define deb2(x, y)              cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x)                  x.begin(), x.end()
#define lb(a,x)                 lower_bound(all(a),x)
#define ub(a,x)                 upper_bound(all(a),x)

typedef priority_queue<int>     maxHeap;
typedef priority_queue<int,     vector<int>, greater<int>> minHeap;
typedef pair<int, int>          pii;
typedef vector<int>             vi;
typedef vector<string>          vs;
typedef vector<pii>             vpii;
typedef vector<vi>              vvi;
typedef map<int, int>            mpii;
typedef set<int>                seti;
typedef multiset<int>           mseti;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
// typedef long int                ld;
// typedef unsigned long int       lu;
// typedef long long int           ll;
// typedef unsigned long long int  llu;


// cout << fixed << setprecision(9) <<
int mpow(int base, int exp);

const int T2 = 105; const int T3 = 1005; const int T4 = 10005; const int T5 = 100005;
const int N = 20;
int n, m;
bool edge[N][N];
int dp[(1 << N)];

void solve() {
    cin >> n >> m;
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        edge[a][b] = 1;
        edge[b][a] = 1;
    }
    for (int i = 0; i < (1 << n); i++) {
        dp[i] = 1;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j))
                for (int k = j + 1; k < n; k++) {
                    if (i & (1 << k))
                        if (!edge[j][k])
                            dp[i] = MAX;
                }
        }
        for (int j = (i - 1) & i; j; j = (j - 1) & i)
            dp[i] = min(dp[i], dp[j] + dp[i ^ j]);
    }
    cout << dp[(1 << n) - 1] << endl;

}




int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
#endif
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++) {

        // cout<<"Case #"<<i<<": ";

        solve();


    }
    return 0;
}

int mpow(int base, int exp) {
    base %= mod;
    int result = 1;
    while (exp > 0) {
        if (exp & 1) result = ((int)result * base) % mod;
        base = ((int)base * base) % mod;
        exp >>= 1;
    }
    return result;
}


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz(a) int(a.size())
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) { out << "(" << a.first << "," << a.second << ")"; return out; }
template <typename T, size_t N> ostream& operator <<(ostream& out, const array<T, N>& a) { out << "["; bool first = true; for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]"; return out; }
template <typename T> ostream& operator <<(ostream& out, const vector<T>& a) { out << "["; bool first = true; for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]"; return out; }
template <typename T, class Cmp> ostream& operator <<(ostream& out, const set<T, Cmp>& a) { out << "{"; bool first = true; for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}"; return out; }
template <typename U, typename T, class Cmp> ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) { out << "{"; bool first = true; for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}"; return out; }
template <typename Arg1> void __f(const char* name, Arg1&& arg1){ cerr << name << ": " << arg1 << endl; }
template <typename Arg1, typename... Args> void __f(const char* names, Arg1&& arg1, Args&&... args){ const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << ": " << arg1 << " |"; __f(comma + 1, args...); }

#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif

void solve() {
	int n, m; cin >> n >> m;
	vector<int> sub(1<<n);
	for(int i=0; i<m; i++) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		for(int k=1; k<(1<<n); k++) {
			if((k&(1<<a)) and (k&(1<<b))) {
				++sub[k];
			}
		}
	}
	vector<bool> valid(1<<n);
	for(int i=1; i<(1<<n); i++) {
		int cnt = bitset<32>(i).count();
		if((cnt*(cnt-1))/2 == sub[i]) {
			valid[i] = true;
		}
	}
	vector<int> dp(1<<n, 1e9);
	dp[0] = 0;
	for(int i=1; i<(1<<n); i++) {
		if(valid[i]) {
			dp[i] = 1;
		} else {
			for(int j=i; j; j=(j-1)&i) {
				dp[i] = min(dp[i], dp[j] + dp[i^j]);
			}
		}
	}
	cout << dp[(1<<n)-1] << endl;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}

