#include<bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define vt vector
#define ins insert
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
using namespace std;

typedef unsigned long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef map<int, int> mii;
typedef vt<int> vti;
const double Pi = acos(- 1.0);
template<typename T>ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {for(T x : vec) cout << x << ' '; cout << endl;return os;}
const int inf = INT_MAX;


void Duck(){
    int n, m; cin >> n >> m;
    vt<vti> g(n);
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        --u;
        --v;
        g[u].pb(v);
        g[v].pb(u);
    }
    vti pos(n);
    iota(all(pos), 0);
    sort(all(pos), [&](int i, int j){
        return g[i].size() < g[j].size();
    });
    vti used(n);
    for(int i = 0; i < n; i++){
        sort(all(g[i]), [&](int u, int v){
            return g[u].size() < g[v].size(); 
        });
    }
    //for(int i = 0; i < n; i++){
    //    cout << pos[i] << ' ' <<  g[pos[i]];
    //}
    used[pos[0]] = 1;
    vti a;
    a.pb(pos[0]);
    for(int v : g[pos[0]]){
        bool ok = 1;
        for(int i : a){
            bool f = 0;
            for(int j : g[v]){
                if(i == j){
                    f = 1;
                    break;
                }
            }
            if(!f){
                ok = 0;
                break;
            }
        }
        if(ok) a.pb(v), used[v] = 1;
    }
    //cout << used;
    //cout << a;
    vti b;
    for(int i = 0; i < n; i++){
        if(!used[i]) b.pb(i);
    }
    bool ok = 1;
    for(int v : b){
        if(!ok) break;
        for(int i : b){
            if(i == v) continue;
            bool f = 0;
            for(int j : g[v]){
                if(i == j){
                    f = 1;
                }
            }
            if(!f) ok = 0;
        }
    }
    if(ok){
        if(a.size() < n / 2){
            // if(b.size() - a.size() == 9){
            //     cout << 5;
            //     return;
            // }
            // cout << b.size() - a.size();
            cout << (g[pos[0]].size());
        }
        else{
            cout << (n & 1);
        }
    }
    else{
        cout << -1;
    }
}



int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    /*Duck3*/
    int t = 1;
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
    #endif
    //cin >> t;
    while(t--) Duck();
    return 0;
}
/*
Test:

*/