#include <bits/stdc++.h>
using namespace std;
#define getbit(n, i) (((n) & (1LL << (i))) != 0) 
#define setbit0(n, i) ((n) & (~(1LL << (i)))) 
#define setbit1(n, i) ((n) | (1LL << (i))) 
#define togglebit(n, i) ((n) ^ (1LL << (i))) 
#define lastone(n) ((n) & (-(n))) 
char gap = 32;
#define int long long
#define ll long long 
#define lll __int128_t
#define pb push_back

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1005;

vector<int> adj[N];
set<int> st[N];
int pushed[N];
bool cmp(int a, int b) {
    return adj[a].size() < adj[b].size();
}

set<int> recurse(vector<int> v){
    //for(auto vv:v) cout<<vv<<" ";
    //cout<<endl;
    
    shuffle(v.begin(),v.end(),rng);

    

    

    int a=-1,b=-1;
    for(int i=0;i<v.size();i++){
        if( st[v[i]].size()+1 != v.size() ) {
            a = v[i];
            for(auto j:v){
                if( j == a ) continue;
                if(st[a].count(j) == 0){
                    b = j;
                    break;
                }
            }
            break;
        }
    }


    if( a == -1 ){
        set<int> ret;
        for(int i=0;i<v.size();i++){
            ret.insert(i);
        }
        return ret;
    }
    //cout<<"de "<<a<<" "<<b<<endl;
    int n = v.size();
    vector<int> va,vb,vc,vall;

    va.push_back(a);
    vb.push_back(b);
   // cout<<"de "<<a<<" "<<b<<endl;
   // shuffle(v.begin(),v.end(),rng);

    vector<int> nxt;

    while(true){
        bool flag = true;
        nxt.clear();
        for(auto i:v){
            if( i == a ) continue;
            if( i == b ) continue;
            
            bool posa = true;
            bool posb = true;

            for(auto x:va){
                if( st[i].count(x) == 0 ){
                    posa = false;
                    break;
                }
            }

            for(auto x:vb){
                if( st[i].count(x) == 0 ){
                    posb = false;
                    break;
                }
            }

            if( posa and !posb ){
                //cout<<"inserted in va "<<i<<endl;
                va.push_back(i);
                flag = false;
                continue;
            }
            if( posb and !posa ){
               // cout<<"inserted in vb "<<i<<endl;
                vb.push_back(i);
                flag = false;
                continue;
            }

            if( !posa and !posb ){
                cout<<-1;
                exit(0);
            }

            nxt.push_back(i);
        
        }

        if( flag == true ) break;
        v = nxt;

    }

    if( nxt.size()){
        for(int i=0;i<va.size();i++){
            for(auto v:st[va[i]]) st[v].erase(va[i]);
        }
        for(int i=0;i<vb.size();i++){
            for(auto v:st[vb[i]]) st[v].erase(vb[i]);
        }
        set<int> ret = recurse(nxt);
        set<int> ret2;
        for(auto r:ret) {
            //cout<<r<<"< ";
            ret2.insert(r+va.size());
            ret2.insert(r+vb.size());
        }
        return ret2;
    }else{
        return {(int)va.size(),(int)vb.size()};
    }
    return {};
}

void solve() {
    int n, m;
    cin>>n>>m;
    for (int i=0; i<m; i++) {
        int u, v;
        cin>>u>>v;
        adj[u].pb(v);
        adj[v].pb(u);
        st[u].insert(v);
        st[v].insert(u);
    }
    
    if( m == n*(n-1)/2 ){
        cout<<n%2;
        return;
    }
    vector<int> v;
    for(int i=1;i<=n;i++) v.pb(i);
    set<int> ret = recurse(v);

    int mn = 1e9;
    cout<<endl;
    for(auto r:ret){
       // cout<<r<<"<< ";
        mn = min(mn,abs(n-2*r));
    }

    cout<<mn;
    
/*
    // for(auto a:va) cout<<a<<" "; cout<<endl;
    // for(auto a:vb) cout<<a<<" "; cout<<endl;
    // cout<<endl;

    for(int i=0;i<va.size();i++){
        for(int j=i+1;j<va.size();j++){
            if( st[va[i]].count(va[j]) == 0 ){
               // cout<<"aa "<<va[i]<<" "<<va[j]<<endl;
                cout<<-1;
                return;
            }
        }
    }
    
    for(int i=0;i<vb.size();i++){
        for(int j=i+1;j<vb.size();j++){
            if( st[vb[i]].count(vb[j]) == 0 ){
                cout<<-1;
                return;
            }
        }
    }

    

    sort(vc.begin(),vc.end(),cmp);
    for(int it=0;it<vc.size();it++){
        int c = vc[it];
    //    cout<<"de "<<c<<" ";
        bool posa = true;
        for(auto x:va){
            if( st[c].count(x) == 0 ){
                posa = false;
                break;
            }
        }
        
        bool posb = true;
        for(auto x:vb){
            if( st[c].count(x) == 0 ){
                posb = false;
                break;
            }
        }
        if(posb and !posa){
            vb.push_back(c);
            continue;
        }
        if(posa and !posb){
            va.push_back(c);
            continue;
        }
        if( posa and posb ){
            if(pushed[c]>=10){
                if( va.size() >= vb.size() ) vb.push_back(c);
                else va.push_back(c);
                
            }else{
                pushed[c]++;
                vc.push_back(c);
            }
            
            continue;
        }
        cout<<-1;
        return;
    }
    while(vall.size()){
        if( va.size()>=vb.size() ){
            vb.push_back(vall.back());
            vall.pop_back();
        } else{
            va.push_back(vall.back());
            vall.pop_back();
        }
    }

    cout<<abs((int)va.size()-(int)vb.size())<<endl;
    */

}
signed main(){
    // ios_base::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    
    solve();
    return 0;
}