#include <bits/stdc++.h>

#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; i--)
#define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); i--)
#define all(a) a.begin(), a.end()
#define SZ(a) ll(a.size())
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;

template<typename T>
struct SegmentTree{
    ll N;
    T INF;
    vector<T> node;
    SegmentTree(ll n, T INF_):INF(INF_){
        N = 1;
        while(N <= n) N <<= 1;
        node.resize(2*N, INF);
    }
    T compare(T A, T B){
        return max(A, B);
    }
    void update(ll index, T val){
        index += N;
        node[index] = val;
        while(index > 0){
            index >>= 1;
            node[index] = compare(node[index*2], node[index*2+1]);
        }
    }
    T calc(ll left, ll right){
        T ret = INF;
        left += N;
        right += N;
        while(left < right){
            if(left & 1) ret = compare(ret, node[left++]);
            if(right & 1) ret = compare(ret, node[--right]);
            left >>= 1;
            right >>= 1;
        }
        return ret;
    }
};

constexpr ll inf = LLONG_MAX/4;
SegmentTree<P> seg(0, make_pair(-inf, -inf));
ll n;
vvl edge;
vl cnt;
vector<bool> used;

void deactivate(ll now){
    assert(!used[now]);
    seg.update(now, make_pair(-inf, now));
    used[now] = true;
    for(auto next: edge[now]){
        if(used[next]) continue;
        cnt[next]--;
        seg.update(next, make_pair(cnt[next],next));
    }
}

void activate(ll now){
    assert(used[now]);
    seg.update(now, make_pair(cnt[now], now));
    used[now] = false;
    for(auto next: edge[now]){
        if(used[next]) continue;
        cnt[next]++;
        seg.update(next, make_pair(cnt[next],next));
    }
}

ll dfs(ll remain){
    if(remain < 0) return -inf;
    auto p = seg.calc(0, n);
    if(p.first <= 0){
        return remain;
    }
    if(p.first <= 2){
        vl cand;
        rep(_,remain*3){
            p = seg.calc(0, n);
            if(p.first <= 0) break;
            seg.update(p.second, make_pair(-inf, p.second));
            cand.eb(p.second);
        }
        p = seg.calc(0, n);
        if(p.first > 0){
            for(auto s: cand) seg.update(s, make_pair(cnt[s], s));
            return -inf;
        }
        for(auto s: cand){
            if(used[s]) continue;
            ll visited = 0;
            queue<ll> que;
            que.push(s);
            bool isCycle = true;
            used[s] = true;
            while(!que.empty()){
                ll now = que.front(); que.pop();
                if(cnt[now] == 1) isCycle = false;
                visited++;
                for(auto next: edge[now]){
                    if(used[next]) continue;
                    que.push(next);
                    used[next] = true;
                }
            }
            if(isCycle) remain -= (visited+1)/2;
            else remain -= visited/2;
        }
        for(auto s: cand){
            seg.update(s, make_pair(cnt[s], s));
            used[s] = false;
        }
        return remain;
    }
    ll ret = -inf;
    ll now = p.second;
    if(p.first <= remain){
        deactivate(now);
        vl visited;
        for(auto next: edge[now]){
            if(used[next]) continue;
            visited.eb(next);
            deactivate(next);
        }
        ret = max(ret, dfs(remain-p.first));
        reverse(all(visited));
        for(auto next: visited) activate(next);
        activate(now);
    }
    deactivate(now);
    ret = max(ret, dfs(remain-1));
    activate(now);
    return ret;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    cout << std::fixed << std::setprecision(15);
    ll m; cin >> n >> m;
    edge.resize(n);
    rep(i,m){
        ll x,y; cin >> x >> y;
        edge[x].eb(y);
        edge[y].eb(x);
    }
    cnt.resize(n);
    seg = SegmentTree<P>(n, make_pair(-inf, -inf));
    rep(i,n){
        cnt[i] = SZ(edge[i]);
        seg.update(i, make_pair(cnt[i],i));
    }
    used.resize(n);
    ll ans = n-29+dfs(29);
    if(ans < n-28) ans = -1;
    cout << ans << endl;
}