#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, vti(n));
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        --u, --v;
        g[u][v] = 1;
        g[v][u] = 1;
    }
    //cout << g;
    vti color(n), vis(n);
    int cnt = 0;
    int check = 1;
    function<void(int)> dfs = [&](int u){
        vis[u] = 1;
        //cout << u << ' ';
        if(color[u]) {
            cnt++;
        }
        else{
            cnt--;
        }
        for(int v = 0; v < n; v++){
            if(v == u) continue;
            if(g[v][u]) continue;
            if(!vis[v]){
                color[v] = color[u] ^ 1;
                dfs(v);
            }
            else{
                if(color[v] == color[u]){
                    //cout << debug(v) debug(u) << endl;
                    check = 0;
                }
            }
        }
    };
    vti f;
    
    for(int i = 0; i < n; i++){
        if(!vis[i]){
            dfs(i);
            f.pb(abs(cnt));
            cnt = 0;
            //cout << endl;
        }
    }
    //cout << f;
    if(!check){
        cout << -1;
    }
    else{
        vti dp(2 * n + 1, 0);
        dp[0] = 1;
        for(int x : f){
            vti ndp(2 * n);
            for(int i = x; i <= n; i++){
                ndp[i] = dp[i - x];
            }
            for(int i = x; i <= n; i++){
                ndp[i] |= dp[i + x];
            }
            dp = ndp;
        }
        //cout << dp;
        for(int i = 0; i < n; i++){
            if(dp[i]){
                cout << i;
                return;
            }
        }
        
    }
    

}



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:

*/