/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

ll S3(ll N, ll S){
    ll md = (3 + 3*N) >> 1;
    if(S > md) S = 3*N - S + 3;
    S -= 2;
    if(S <= N) return S*(S+1) / 2;
    ll res = N*(N+1) / 2;
    S -= N;
    res += (S*N - S*(S+1));
    return res;
}

ll S2(ll N, ll S){
    if(S == 1 || S > 2*N) return 0;
    if(S <= N+1) return S - 1;
    return 2*N - S + 1;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    ll N, K; cin >> N >> K;

    ll S = -1;
    for(int i=3; i<=3*N; i++){
        if(S3(N, i) < K) K -= S3(N, i);
        else{ S = i; break; }
    }

    ll A;
    for(int i=1; i<=N; i++){
        if(S2(N, S-i) < K) K -= S2(N, S-i);
        else{ A = i; break; }
    }

    for(int i=1; i<=N; i++){
        int a = i, b = S-A-i;
        if(a < 1 || b < 1 || a > N || b > N) continue;
        if(!--K) cout << A << " " << a << " " << b;
    }
}
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;
const int INF = 0xccccccc;
const ll LINF = 0xcccccccccccccccLL;
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}
template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}
template<typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}

const unsigned int mod = 1000000007;
//const unsigned int mod = 998244353;

struct mint {
  unsigned int x;
  mint():x(0) {}
  mint(int64_t x_) {
    int64_t v = int64_t(x_ % mod);
    if(v < 0) v += mod;
    x = (unsigned int)v;
  }
  static mint row(int v) {
    mint v_;
    v_.x = v;
    return v_;
  }
  mint operator-() const { return mint(-int64_t(x));}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    uint64_t z = x;
    z *= a.x;
    x = (unsigned int)(z % mod);
    return *this;
  }
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  friend bool operator==(const mint &a, const mint &b) {return a.x == b.x;}
  friend bool operator!=(const mint &a, const mint &b) {return a.x != b.x;}
  mint &operator++() {
    x++;
    if(x == mod) x = 0;
    return *this;
  }
  mint &operator--() {
    if(x == 0) x = mod;
    x--;
    return *this;
  }
  mint operator++(int) {
    mint result = *this;
    ++*this;
    return result;
  }
  mint operator--(int) {
    mint result = *this;
    --*this;
    return result;
  }
  mint pow(int64_t t) const {
    mint x_ = *this, r = 1;
    while(t) {
      if(t&1) r *= x_;
      x_ *= x_;
      t >>= 1;
    }
    return r;
  }
  //for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) {return mint(*this) /= a;}
};

istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

string to_string(mint a) {
  return to_string(a.x);
}

//head



int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vi e(n);
  rep(i, m) {
    int a, b;
    cin >> a >> b;
    a--; b--;
    e[a] ^= 1<<b;
    e[b] ^= 1<<a;
  }
  vi I(1<<n);
  I[0] = 1;
  for(int i = 1; i < 1<<n; i++) {
    int u = __builtin_ctz(i);
    I[i] = I[i^(1<<u)] + I[e[u]&i];
  }
  vector<mint> f(1<<n, mint(1));
  for(int k = 1; k < n; k++) {
    rep(i, 1<<n) f[i] *= I[i];
    mint now;
    rep(i, 1<<n) {
      if(__builtin_popcount(i)&1) now += f[i];
      else now -= f[i];
    }
    if(now.x) {
      cout << k << endl;
      return 0;
    }
  }
  cout << n << endl;
}