#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define vi vector<int>
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define per(i,b,a) for(int i = b-1; i >= a; --i)

#define debug(...) 42;
#ifdef LOCAL
#include "debug.h"
#endif

struct DSU {
    int n;
    vector<int> p, sz;
    DSU(int _n) {
        n = _n;
        p.resize(n);
        sz.resize(n, 1);
        iota(all(p), 0);
    }
    int leader(int u) { return u == p[u] ? u : p[u] = leader(p[u]); }
    bool merge(int u, int v) {
        int a = leader(u), b = leader(v);
        if (a != b) {
            // if (sz[a] < sz[b]) swap(a, b);
            p[b] = a;
            sz[a] += sz[b];
            return true;
        }
        return false;
    }
    int size(int u){
        return sz[leader(u)];
    }
};

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int n, m; cin >> n >> m;
    vector<vi> adj(n+1);
    rep(i,0,m){
        int u, v; cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    if(n <= 3){
        cout << -1 << '\n';
        return 0;
    }

    map<pii, int> check;
    int odd = 0, even = 0;
    int idx = 0;
    vi color(n+1, -1), dfn(n+1);
    function<void(int, int)> dfs = [&](int u, int c){
        color[u] = c;
        dfn[u] = ++idx;
        for(int v: adj[u]) if(color[v] == -1){
            dfs(v, c^1);
        }else{
            if(color[v] == color[u]^1){
                cout << dfn[u] << ' ' << dfn[v] << '\n';
                assert((dfn[u] - dfn[v] + 1) % 2 == 0);
                if(dfn[u] - dfn[v] + 1 >= 4) even = 1;
            }else{
                odd = 1;
                if(check.count({u, v})){
                    even = 1;
                }
                check[{u, v}] = 1;
            }
        }
    }; rep(i,1,n+1) if(color[i] == -1) dfs(i, 0);

    DSU dsu(n+1);
    vector<int> comp(n+1);
    rep(u,1,n+1) for(int v: adj[u]) dsu.merge(u, v);
    rep(i,1,n+1) comp[dsu.leader(i)]++;

    int ans;
    if(even and odd){
        ans = 0;
    }
    if(even and !odd){
        ans = 1;
    }
    if(!even and odd){
        bool more = false;
        rep(i,1,n+1) if(comp[i] > 3) more = true;
        if(more) ans = 1;
        else ans = 2;
    }
    if(!even and !odd){
        sort(all(comp));
        int cur = 0;
        per(i,n+1,1){
            cur += comp[i];
            ans++;
            if(cur >= 4) break;
        }
        ans += 2-1;
    }
    cout << ans << '\n';

    return 0;
}