#include<assert.h>
#include<stack>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
#define eprintf(s...)  fprintf(stderr, s)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }

int N, M;

VI G[100111];
int deg[100111];
int C_sum;
int C[100111];
bool use[100111];
int A[100111], B[100111];
LL dp[100111];

VI ord;
void color() {
    ord.reserve(N);
    ord.push_back(0);
    C_sum = 1;
    C[0] = 1;

    REP (_, N) {
	int v = ord[_];

	EACH (e, G[v]) {
	    G[*e].erase(remove(G[*e].begin(), G[*e].end(), v), G[*e].end());

	    if (C[v] == 1) {
		C_sum--;
		C[*e] = -1;
	    } else {
		C_sum++;
		C[*e] = 1;
	    }

	    ord.push_back(*e);
	}
    }
}
LL solve() {
    LL ret = 0;
    REP (_, N) {
	int v = ord[N-1-_];
	dp[v] = C[v];
	EACH (e, G[v]) {
	    dp[v] += dp[*e];
	}

	ret += abs(C_sum - 2 * dp[v]);
    }

    assert(ret % 2 == 0);
    return ret / 2;
}

int main() {
    scanf("%d%d", &N, &M);
    REP (i, M) {
	scanf("%d%d", A+i, B+i);
	A[i]--;
	B[i]--;
	G[A[i]].push_back(B[i]);
	G[B[i]].push_back(A[i]);
    }

    LL ans = 0;

    if (M == N - 1) {
	color();
	if (C_sum) {
	    ans = -1;
	} else {
	    ans = solve();
	}
    } else {

	stack<int> S;
	REP (i, N) {
	    deg[i] = G[i].size();
	    if (deg[i] == 1) S.push(i);
	}

	while (!S.empty()) {
	    int v = S.top(); S.pop();

	    use[v] = true;

	    EACH (e, G[v]) {
		deg[*e]--;
		if (deg[*e] == 1) S.push(*e);
	    }
	}


	int root = 0;
	REP (i, N) if (!use[i]) {
	    root = i;
	    break;
	}

	int cur = root;
	VI X;
	while (true) {
//	    eprintf("%d %d", cur, C[cur]); eprintf("\n");
	    X.push_back(cur);
	    use[cur] = true;

	    bool update = false;
	    EACH (e, G[cur]) if (!use[*e]) {
		cur = *e;
		update = true;
		break;
	    }

	    if (!update) break;
	}

	int x0 = X[0], x1 = X[1];
	G[x0].erase(remove(G[x0].begin(), G[x0].end(), x1), G[x0].end());
	G[x1].erase(remove(G[x1].begin(), G[x1].end(), x0), G[x1].end());


	color();

	if (X.size() & 1) {
	    if (C_sum & 1) {
		ans = -1;
	    } else {
		C[x0] -= C_sum / 2;
		C[x1] -= C_sum / 2;
		ans = abs(C_sum) / 2;
		C_sum = 0;
		ans += solve();
	    }
	} else {

	    if (C_sum != 0) {
		ans = -1;
	    } else {
		int lo = -N, hi = N;

		while (hi - lo > 2) {
		    int llh = (lo + lo + hi) / 3;
		    int lhh = (lo + hi + hi) / 3;
		    C[x0] -= llh;
		    C[x1] += llh;
		    LL tmp_0 = solve() + abs(llh);
		    C[x0] += llh;
		    C[x1] -= llh;

		    C[x0] -= lhh;
		    C[x1] += lhh;
		    LL tmp_1 = solve() + abs(lhh);
		    C[x0] += lhh;
		    C[x1] -= lhh;


		    if (tmp_0 < tmp_1) hi = lhh;
		    else lo = llh;
		}

		ans = 1LL<<60;
		for (int i=lo; i<=hi; i++) {
		    C[x0] -= i;
		    C[x1] += i;
		    LL tmp = solve() + abs(i);
		    C[x0] += i;
		    C[x1] -= i;
		    amin(ans, tmp);
		}
	    }
	}
    }

    printf("%lld\n", ans);


    return 0;
}



Measured memory_bytes: 9336