#include <bits/stdc++.h>

using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int, int>
const int N = 1e3 + 10;
int n, m, dp[2][N], vis[N];
vector<int> e[N];
vector<int> tmp, g[N];

void dfs(int u)
{
    tmp.push_back(u);
    for (auto to : g[u])
        if (!vis[to])
            vis[to] = 3 ^ vis[u], dfs(to);
        else if (vis[to] == vis[u])
        {
            cout << -1 << endl;
            exit(0);
        }
}

int top = 0;
PII stk[N];

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        e[i].resize(n + 1), fill(e[i].begin(), e[i].end(), 1);
    for (int i = 1; i <= n; i++)
        e[i][i] = 0;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[u][v] = 0, e[v][u] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (e[i][j])
                g[i].push_back(j);
        }
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
        {
            vis[i] = 1;
            tmp.clear();
            dfs(i);
            int cnt = 0;
            for (auto to : tmp)
                if (vis[to] == 1)
                    cnt++;
            stk[++top] = {cnt, tmp.size() - cnt};
        }
    dp[0][0] = 1;
    for (int i = 1; i <= top; i++)
    {
        for (int j = n; j >= stk[i].first; j--)
            dp[i & 1][j] |= dp[1 ^ (i & 1)][j - stk[i].first];
        for (int j = n; j >= stk[i].second; j--)
            dp[i & 1][j] |= dp[1 ^ (i & 1)][j - stk[i].second];
    }
    int ans = n;
    for (int i = 1; i <= n / 2; i++)
        if (dp[n & 1][i])
            ans = min(ans, n - i - i);
    cout << ans << endl;
}

signed main()
{
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
    return 0;
}