#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef unordered_map<int,int> umap;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define popcount __builtin_popcount
#define case cout<<"Case "<<__testcase-testcase<<":";
#define endl '\n'
vector<vii> g;
vii v;
int w,b;
bool dfs(int u,int p,int c){
    if(v[u]>-1 && v[u]==c) return false;
    else if(v[u]==1-c) return true;
    v[u]=c;
    if(c==0) w++;
    else b++;
    for(auto i: g[u]) if(i!=p) if(dfs(i,u,1-c)) return true;
    return false;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int testcase=1;
    //cin>>testcase;
    int __testcase=testcase;
    while(testcase--){
        int n,m,i,j,k;
        cin>>n>>m;
        int e[n+5][n+5];
        for(i=0;i<n+5;i++) for(j=0;j<n+5;j++) e[i][j]=0;
        while(m--){
            int u,v;
            cin>>u>>v;
            e[u][v]=1;
            e[v][u]=1;
        }
        g.resize(n+5);
        v.assign(n+5,-1);
        for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(e[i][j]==0 && i!=j) g[i].pb(j);
        vii p;
        int one=0;
        for(i=1;i<=n;i++){
            if(v[i]>=0) continue;
            w=b=0;
            if(dfs(i,-1,0)) break;
            if(w!=b) p.pb(abs(w-b));
        }
        if(i<=n){
            cout<<-1<<endl;
            continue;
        }
        int total=0; for(auto i: p) total+=i;
        n=p.size();
        m=total/2;
        int dp[2][m+5];
        for(i=0;i<=m;i++) dp[1][i]=0;
        dp[1][0]=1;
        int idx, pre;
        for(i=0;i<n;i++){
            idx=i%2;
            pre=1-idx;
            for(j=0;j<=m;j++) dp[idx][j]=0;
            for(j=0;j<=m;j++){
                if(j+p[i]<=m) dp[idx][j+p[i]]|=dp[pre][j];
                dp[idx][j]|=dp[pre][j];
            }
        }
        //for(auto i: p) cout<<i<<" "; cout<<endl;
        int ans=n;
        for(i=0;i<=m;i++) if(dp[idx][i]) ans=min(ans,total-2*i);
        cout<<ans<<endl;

    }
}