#define _CRT_SECURE_NO_WARNINGS

#include <bits/stdc++.h>

#define TASK "kcolors"

using namespace std;

typedef int ll;
typedef long double ld;
#define all(x) (x).begin(),(x).end()
#define sz(x) ((long long)(x).size())
#define elif else if
const ld eps = 1e-9;
const ll inf = numeric_limits<ll>::max() / 2 - 1;
const ll mod = 1000000007;
const ll maxn = 14;
const ll maxm = 23456;
/*
char mem[200000000];
int mpos = 0;

void *operator new(size_t n) {
    void *ans = mem + mpos;
    if (mpos + n >= 200000000) mpos = 0;
    mpos += n;
    return ans;
}

void operator delete(void *p) {}*/
#define int char

vector<int> edges[maxn];
vector<int> pedges[maxn];
vector<int> color;
int ans = 13;

inline void ae(int a, int b) {
    edges[a].push_back(b);
    pedges[b].push_back(a);
}

inline bool dfs(int v, const int &k, bool is0) {
    if (clock() * 1000 / CLOCKS_PER_SEC > 1950) {
        cout << (long long) ans;
        exit(0);
    }
    vector<bool> can(k, 1);
    for (auto i : edges[v]) {
        if (color[i] != -1) can[color[i]] = 0;
    }
    if (can.empty()) return false;
    for (int c = 0; c < (is0 ? 1 : k); ++c) {
        if (!can[c]) continue;
        color[v] = c;
        bool ans = true;
        for (auto i : edges[v]) {
            if (color[i] == -1) {
                ans = dfs(i, k, 0);
                if (!ans) break;
            }
        }
        if (ans) return true;
    }
    color[v] = -1;
    return false;
}

inline int run() {
    ll n, m;
    cin >> n >> m;
    color.assign(n, -1);
    for (int i = 0; i < m; ++i) {
        ll a, b;
        cin >> a >> b;
        a--;
        b--;
        ae(a, b);
        ae(b, a);
    }
    ans = 13;
    while (ans != 1) {
        int k = ans - 1;
        bool bans = true;
        color.assign(n, -1);
        for (int i = 1; i < n; ++i) {
            if (color[i] == -1) {
                if (!dfs(i, k, 1)) {
                    bans = false;
                    break;
                }
            }
        }
        if (!bans) {
            cout << (long long) ans;
            return 0;
        }
        ans--;
    }
    cout << (long long) ans;
    return 0;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#else
    if (strlen(TASK) > 0) {
        freopen(TASK".in", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
#endif
    run();
    return 0;
}