#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

#include <bits/stdc++.h>

using namespace std;
int mp[101][101], n, m, ans = 0x3f3f3f3f;
int arr[101][101];
int cnt[101];

void dfs(int p, int r) {
    if (r >= ans) return;
    if (p > n)
        ans = min(ans, r);
    else {
        for (int i = 1; i <= r; i++) {
            bool flag = true;
            for (int j = 0; j < cnt[i] && flag; j++)
                if (mp[p][arr[i][j]])
                    flag = false;
            if (flag) {
                arr[i][cnt[i]++] = p;
                dfs(p + 1, r);
                cnt[i]--;
            }
        }
        arr[r + 1][cnt[r + 1]++] = p;
        dfs(p + 1, r + 1);
        cnt[r + 1]--;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, a, b; i < m; i++)
        scanf("%d%d", &a, &b), mp[a][b] = mp[b][a] = 1;
    dfs(1, 0);
    printf("%d", ans);
    return 0;
}