#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define sp ' '
#define endl '\n'
#define loop(i, l, r) for(int i=(int)(l); i<=(int)(r); i++)
#define all(x) (x).begin(), (x).end()

const int N = 1005;

struct SolverGraph{
    int n,m;
    bool mark[N][N];
    int color[N];
    vector<vector<int> > a;

    SolverGraph(){
        memset(mark,0,sizeof mark);
        memset(color,-1,sizeof color);
        a.assign(N,vector<int>());
    }

    void genComp(){
        loop(i,1,n){
            loop(j,1,n){
                if (i==j||mark[i][j]==true) continue;
                a[i].push_back(j);
            }
        }
    }

    int colorComp(int root){
        int ret = 0;
        queue<int> q; q.push(root); color[root] = 0;
        while(!q.empty()){
            auto u = q.front(); q.pop();
            if (color[u]==0) ret++;
            for(auto v:a[u]){
                if (color[v]==-1) {
                    color[v] = color[u] ^ 1;
                    q.push(v);
                }
                else{
                    if (color[v]!=(color[u]^1)){
                        return -1;
                    }
                }
            }
        }
        return ret;
    }

    pair<int,vector<int>> operator()(){
        cin >> n >> m;
        loop(i,1,m){
            int u,v; cin >> u >> v;
            mark[u][v] = mark[v][u] = true;
        }
        genComp();

        vector<int> ret;
        loop(i,1,n){
            if (color[i]==-1){
                auto rec = colorComp(i);
                if (rec==-1){
                    return {-1,{}};
                }
                ret.push_back(rec);
            }
        }
        return {n,ret};
    }
};

struct SolverKnapsack{
    int total;
    vector<int> a;
    bool dp[N][N];
    SolverKnapsack(int _total, vector<int> _a):total(_total),a(_a){
        memset(dp,0,sizeof dp);
    };

    int operator()(){
        // return the smallest diff
        dp[0][0] = true;
        loop(i,1,a.size()){
            int item = a[i-1];
            loop(j,item,total){
                if (dp[i-1][j-item]){
                    dp[i][j] = true;
                    break;
                }
            }
        }

        int ans = total;
        loop(i,0,total){
            if (dp[a.size()][i]==false) continue;
            ans = min(ans,abs(i-(total-i)));
        }
        return ans;
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifdef LOCAL
    freopen("1test.inp","r",stdin);
#endif
    SolverGraph solve1;
    auto [n,whites] = solve1();
    if (n==-1){
        cout << -1 << endl;
        return 0;
    }

    SolverKnapsack solve2(n,whites);
    cout << solve2() << endl;
}