#include <bits/stdc++.h>
using namespace std;
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
*/

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template <class T> using PQMax = priority_queue<T>;
template <class T> using PQMin = priority_queue<T, vector<T>, greater<T>>;
template <class T1, class T2>
void maximize(T1 &a, T2 b){
    if (b > a) a = b;
}
template <class T1, class T2>
void minimize(T1 &a, T2 b){
    if (b < a) a = b;
}
template <class T>
void read(T &number)
{
    bool negative = false;
    register int c;
    number = 0;
    c = getchar();
    while (c != '-' && !isalnum(c)) c = getchar();
    if (c=='-'){
        negative = true;
        c = getchar();
    }
    for (; (c>47 && c<58); c=getchar())
        number = number *10 + c - 48;
    if (negative)
        number *= -1;
}
template <class T, class ...Ts>
void read(T &a, Ts& ... args){
    read(a);
    read(args...);
}

/*
struct Node
{
    int node, len;
    Node() {node = len = 0;}
    Node(int node, int len) {this -> node = node, this -> len = len;}
};
typedef vector<Node> vg;
*/

#define MAX 1000001
#define MOD 1000000007

#define fi first
#define se second

#define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)
#define FORD(type, i, b, a) for(type i = (b); i >= (a); i--)

#define testBit(n, bit) (((n) >> (bit)) & 1)
#define flipBit(n, bit) ((n) ^ (1ll << (bit)))
#define cntBit(n) __builtin_popcount(n)
#define cntBitll(n) __builtin_popcountll(n)
#define randomize mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

randomize;
int n, m;
vector<int> graph[MAX];

bool visited[MAX];
bool isClique[MAX];
inline vector<int> buildClique(int root) {
    memset(visited, false, sizeof(visited));
    memset(isClique, false, sizeof(isClique));
    FOR(int, i, 1, n)
        shuffle(graph[i].begin(), graph[i].end(), mt);
    
    visited[root] = true; isClique[root] = true;
    vector<int> clique; clique.push_back(root);
    
    queue<int> q; 
    for (int child: graph[root]) {
        visited[child] = true;
        q.push(child);
    }

    while (!q.empty()) {
        int node = q.front(); q.pop();
        
        int cnt = 0;
        for (int child: graph[node]) {
            cnt += isClique[child];
        }

        if (cnt == clique.size()) {
            isClique[node] = true;
            clique.push_back(node);
            for (int child: graph[node])
                if (not visited[child]) {
                    visited[child] = true;
                    q.push(child);
                }
        }
    }

    return clique;
}

void input();
main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();

    int minDiff = 1e9;
    FOR(int, times, 1, 50){
        const int root1 = mt() % n + 1;
        vector<int> cl1 = buildClique(root1);

        if (cl1.size() == n) {
            cout << n % 2;
            return 0;
        }

        memset(isClique, false, sizeof(isClique));
        for (int node: cl1) isClique[node] = true;
        int root2 = 0;
        FOR(int, i, 1, n) if (not isClique[i]) {root2 = i; break;}
        vector<int> cl2 = buildClique(root2);



        vector<int> diff1, diff2, same;
        memset(visited, false, sizeof(visited));
        for (int node: cl1) visited[node] = true;
        for (int node: cl2)
            if (visited[node])
                visited[node] = false,
                same.push_back(node);
            else
                diff2.push_back(node);
        for (int node: cl1)
            if (visited[node])
                diff1.push_back(node);
        
        int d1 = diff1.size(), d2 = diff2.size(), s = same.size();
        if (d1 + d2 + s != n) continue; // make new clique

        // for (int node: cl1) cerr << node << ' '; cerr << '\n';
        // // for (int node: cl2) cerr << node << ' '; cerr << '\n';

        if (d1 > d2) swap(d1, d2);
        if (d1 + s >= d2) {
            cout << n % 2;
            return 0;
        }
        minimize(minDiff, d2 - d1 - s);
    }

    if (minDiff == 1e9) cout << -1;
    else cout << minDiff;
}
void input() {
    read(n, m);
    map<pii, bool> oke;
    FOR(int, i, 1, m){
        int u, v; read(u, v);
        if (u > v) swap(u, v);
        oke[{u, v}] = true;
    }
    for (auto x: oke){
        int u = x.fi.fi, v = x.fi.se;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
}