#include <bits/stdc++.h>
using namespace std;
#define int long long
#define el '\n'
const int maxn = 1e3 + 3;
vector<int> e[maxn];
int used[maxn];
bool cmp(const int &u, const int &v) {
    return e[u].size() < e[v].size();
}

void Solve() {
    int n, m; cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    for(int i = 1; i <= n; i++) sort(e[i].begin(), e[i].end(), cmp);

    // for(int i = 1; i <= n; i++) {
    //     cout << i << ": ";
    //     for(int v : e[i]) cout << v << ' ';
    //     cout << el;
    // }

    int id = -1;
    for(int i = 1; i <= n; i++) if(id == -1 | e[id].size() > e[i].size()) id = i;

    used[id] = 1;
    int sz1 = 1;
    for(int v : e[id]) {
        int ok = 0;
        for(int u : e[v]) ok += used[u];
        if(ok == sz1) {
            used[v] = 1;
            ++sz1;
        }
    }

    bool dt2 = 0;
    int sz2 = 0;
    // cout << sz1 << el;
    for(int i = 1; i <= n; i++) if(!used[i]) {
        if (dt2){
            cout << -1;
            return;
        }
        used[i] = 2;
        sz2 = 1;
        for(int v : e[i]) {
            if(used[v]) continue;
            int ok = 0;
            for(int u : e[v]) ok += (used[u] == 2);
            if(ok == sz2) {
                ++sz2;
                used[v] = 2;
            }
        }
        dt2 = true;
    }
    if(sz2 == 0) cout << sz1 % 2;
    else cout << abs(sz1 - sz2);
}
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
// #ifndef ONLINE_JUDGE
//     freopen("inp.txt", "r", stdin);freopen("out.txt", "w", stdout);
// #endif
    int t = 1;// cin >> t;
    while(t--) Solve();
}