#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define fi first
#define se second

using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>,
rb_tree_tag,tree_order_statistics_node_update>;

const int maxn = 1001;

bool color[maxn], c[maxn][maxn], vis[maxn], ok = 0;
int n;
int res;

void dfs(int u) {
    vis[u] = 1;

    if (color[u] == 0) {
        res++;
    }
    else {
        res--;
    }

    for (int i = 0 ; i < n ; i++) {
        if (!c[u][i]) continue;
        if (u == i) continue;
        if (!vis[i]) {
            color[i] = color[u] ^ 1;
            dfs(i);
        }
        else {
            if (color[i] == color[u]) {
                ok = 1;
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0);
    freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);

    int m;

    cin >> n >> m;

    for (int i = 0 ; i < n ; i++) {
        for (int j = 0 ; j < n ; j++) {
            c[i][j] = 1;
        }
    }

    for (int i = 0 ; i < m ; i++) {
        int u, v;

        cin >> u >> v;

        c[u-1][v-1] = c[v-1][u-1] = 0;
    }

    vector<int> bag;

    for (int i = 0 ; i < n ; i++) {
        if (!vis[i]) {
            dfs(i);
            bag.push_back(abs(res));
            res = 0;
        }
    }

    sort(bag.rbegin(), bag.rend());

    bitset<2001> dp, pre;

    pre[0] = 1;

    for (int u: bag) {
        for (int i = u ; i <= 1000 ; i++) {
            dp[i] = pre[i-u];
        }

        for (int i = 0 ; i <= 1000 ; i++) {
            dp[i] = dp[i] | pre[i + u];
        }

        pre = dp;

        dp = 0;
    }

    res = 1E18;

    for (int i = 0 ; i <= 1000 ; i++) {
        if (pre[i]) {
            res = i;
            break;
        }
    }

    if (!ok) {
        cout << abs(res);
    }
    else {
        cout << -1;
    }
    return 0;
}