#include <bits/stdc++.h>
#define REP(i, nn ) for(int i = 0 ; i < (int) nn; i++)
#define REPS(i, ss, nn ) for(int i = ss ; i < (int) nn; i++)
#define REV(i, ss, nn ) for(int i = ss ; i >= nn; i--)
#define deb(x) std::cout << #x << " " << x << endl;
#define debl(x) std::cout << #x << " " << x << " ";
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
namespace std{
    template<class Fun>
    class y_combinator_result{
        Fun fun_;
        public:
            template<class T>
            explicit y_combinator_result(T &&fun) : fun_(std::forward<T>(fun)){}
            template<class ...Args>
            decltype(auto) operator()(Args&&...args){
                return fun_(std::ref(*this), std::forward<Args>(args)...);
            }
    };
    template<class Fun>
    decltype(auto) y_combinator(Fun && fun){
        return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
    }
};
template<typename T>
bool u_max(T& a, T b){
    if( a < b){
        a = b;
        return true;
    }
    return false;
}
template<typename T>
bool u_min(T& a, T b){
    if( a > b){
        a = b;
        return true;
    }
    return false;
}
struct edge{
    int to, from;
    ll cost;
    edge(){ edge(0,0);}
    edge(int to_, ll cost_){ edge(to_, -1, cost_);}
    edge(int to_, int from_, ll cost_) : to(to_), from(from_), cost(cost_){}
    // edge(int to_, int from_) : to(to_), from(from_){};
};

template<typename... T>
void read(T& ... a){
    ((cin >> a),...);
}

void solve(){
    int n, m;
    read(n, m);
    vector<vector<int>> e(n, vector<int>(n, 0));
    REP(i, m){
        int a, b;
        read(a, b);
        a--; b--;
        e[a][b] = e[b][a] = 1;
    }
    int state = 1;
    const int state_num = 1 << n;
    vector<bool> connected(state_num, true);
    auto state_contain = [](int s, int i) -> bool{
        // cout << "test " << s << " " << i << endl;
        // cout << "-> " << ((1<<i) & s ? true : false) << endl;
        return (1<<i) & s ? true : false;
    };
    auto is_connected = [&](int s) -> bool{
        // cout << "test " << s << endl;
        for(int i = 0 ; i < n ; i++){
            for(int j = i+1; j < n ; j++){
                if( ! state_contain(s, i) ) continue;
                if( ! state_contain(s,j) ) continue;
                if(e[i][j] == 0){
                    return false;
                }
            }
        }
        return true;
    };
    vector<int> group(n);
    REP(i, n){
        group[i] = 1 << i;
    }
    REP(ss, state_num){
        connected[ss] = is_connected(ss);
        if(connected[ss]){
            // deb(ss)
            for(int i = 0 ; i < n ; i++){
                if(state_contain(ss, i)) group[i] = ss;
            }
        }
    }
    // cout << "start dp" << endl;

    //max group size
    int INF = 1 << 30;
    vi dp(state_num, INF);
    dp[0] = 0;
    while (state < state_num){
        if(connected[state]){
            dp[state] = 1;
            state++;
            continue;
        }
        // deb(state)
        for(int submask = state; submask; submask=(submask-1)&state){
            dp[state] = min(dp[state], dp[submask] + dp[state^submask]);
        }
        state++;
    }
    cout << dp[state_num-1] << endl;
}

int main()
{
    //making data IO Fast
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    /****************************/
    solve();
    return 0;
}


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

#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
//#define inf 1010000000
#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif
template<typename T> void print(T && x) {cout << x << "\n";}
template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);}

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
const int maxn=100005;
//i_am_noob
int n;

int solve(int x){
    while(x>=n) x-=pow2(__lg(x));
    return x;
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    rep(n) print(solve(i<<1)+1,solve(i<<1|1)+1);
    return 0;
}
