#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<climits>
using namespace std;
//#define int long long
typedef long long ll;
//template<typename T = int>
inline int read(){
    int f = 1,r = 0;
    char c = getchar();
    while(c<'0'||c>'9'){if(c == '-') f = -1; c = getchar();}
    while(c>='0'&&c<='9'){ r = (r<<1) + (r<<3) + c - '0';c = getchar();}
    return f*r;
}
typedef pair<ll,int> PII;
#define fi first
#define se second
#define mst(a,b) memset(a,b,sizeof(a))
#define For(i,a,b) for(int i = a;i<=b;i++)
#define For_(i,a,b) for(int i = a;i>=b;i--)
#define _for(i,a) for(int i = 0;i<a;i++)
#define All(x) x.begin(),x.end()

const int N = 18 ,M = 4e6,INF = 0x3f3f3f3f;

int n,m,t;
int a[(1<<N)+1],g[N+1][N+1],dp[(1<<N) + 1];

signed main(){
    n = read();m = read();
    For(i,1,m){
        int x = read(),y = read();
        g[x][y] = g[y][x] = 1;
    }
    For(S,0,(1<<n)-1){//枚举全部集合
        bool ok = 1;
        For(i,1,n){//判断集合是不是一个完全联通图（把集合中的边完全遍历一遍）都有，是就储存
            if(!(S & (1<<(i-1)))) continue;
            For(j,1,n){
                if(i == j) continue;
                if(!(S & (1<<(j-1)))) continue;
                if(g[i][j] == 0){
                    ok = 0;
                    break;
                }
            }
            if(!ok) break;
        }
        a[S] = ok;
    }
    mst(dp,0x3f);
    dp[0] = 0;
    For(S,1,(1<<n)-1){
        for(int sub = S;sub;sub =(sub-1)&S){
            if(a[sub]) dp[S] = min(dp[S],dp[S ^ sub] + 1);
        }
    }
    cout<<dp[(1<<n)-1]<<"\n";
    return 0;
}


#include <bits/stdc++.h>
using namespace std;
using vi = vector <int>;using vl = vector <long long>;
using vs = vector <string>;using vc = vector <char>;
using ll= long long;using vvl = vector<vector<ll> >;
using vvc = vector<vector<char> >;using vd = vector <double>;
using vpl = vector <pair<ll,ll> >;using vb = vector<bool>;
#define rep(i,r) for(ll i=0;i<(r);i++)
#define Rep(i,l,r) for(ll i=(l);i<(r);i++)
#define print(n) cout<<n<<endl
#define vcin(a) rep(i,a.size())cin>>a[i]
#define sortp(d) sort(d.begin(),d.end()) //1234
#define sortm(d) sort(d.rbegin(),d.rend()) //4321
#define all(n) n.begin(),n.end()
 //各位の和　
int wa(ll x){ll sum = 0;while(x!=0){sum += x% 10;x /= 10;}return sum;}
/*-----------順列生成-----------------
do {
} while (next_permutation(配列変数.begin(), 配列変数.end()));*/
//最大公約数　ユークリッドの互除法
ll gcd(ll a, ll b) {if (b==0) return a;else return gcd(b, a%b);}
//最小公倍数　a*b/gcd
ll lcm(ll a, ll b){return a/gcd(a, b)*b;}
//コンビネーション nCk
ll C(ll n,ll k){ll p=1;rep(i,k)p=p*(n-i)/(i+1);return p;}
//'A'65,'a'97
/*小数点精度指定
cout<<fixed<<setprecision(9)<<;
*/
//priority_queue 優先度付きキュー
ll modpow(ll a,ll n,ll mod) {ll res=1;while(n>0)
{if(n&1)res=res*a%mod;a=a*a%mod;n >>= 1;}return res;}
ll modinv(ll a,ll mod){return modpow(a, mod - 2, mod);}

ll p=0,q=0,r=0;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
#define inf 1000000000000 //10^12:∞
#define mod 1000000007 //10^9+7:合同式の法
const long double pi = acos(-1);

int main()
{ 
  ll n,m;cin>>n>>m;
  print((modpow(10,n,m*m)/m)%m);
}