#include <bits/stdc++.h>

using namespace std;

const int maxn = 100010;

typedef long long ll;

int n, m, l[maxn], deg[maxn], onc[maxn], _vis[maxn], s[maxn], _a[maxn], a[maxn], cnt, e;
int sum[maxn*2], val[maxn];
ll sumi[maxn*2];
ll cost = 0;

struct Edge {
	int v, x;
} E[maxn<<1];

inline void addEdge(int u, int v) {
	E[e].v = v, E[e].x = l[u], l[u] = e++;
}

int dfs(int u, int f, int t = 1) {
	int ret = t;
	for (int p = l[u]; p >= 0; p = E[p].x) {
		int v = E[p].v;
		if (v != f && !onc[v]) {
			ret += dfs(v, u, -t);
		}
	}
	if (f) cost += (ret < 0) ? (-ret) : ret;
	return ret;
}

void findcycle(int u) {
	a[++ cnt] = s[u];
	_vis[u] = 1;
	for (int p = l[u]; p >= 0; p = E[p].x) {
		int v = E[p].v;
		if (onc[v] && !_vis[v]) {
			findcycle(v);
			return;
		}
	}
}

int lowbit(int x) {
	return x & (-x);
}

void add(int p, int v) {
	for (int i = p; i <= 2*n; i+= lowbit(i)) {
		sum[i] += v;
		sumi[i] += (p-n) * v;
	}
}

int ask(int p) {
	int ret = 0;
	for (int i = p; i; i -= lowbit(i)) {
		ret += sum[i];
	}
	return ret;
}

ll aski(int p) {
	ll ret = 0;
	for (int i = p; i; i -= lowbit(i)) {
		ret += sumi[i];
	}
	return ret;
}

ll solve1(int x) {
	ll ret = 0;
	int t = x;
	for (int i = 1; i <= cnt; i++) {
		if (a[i] > 0) {
			int c = min(a[i], t);
			t -= c;
			a[i] -= c;
			ret += 1ll * (i-1) * c;
		}
	}
	t = x;
	for (int i = cnt; i >= 1; i--) {
		if (a[i] > 0) {
			int c = min(a[i], t);
			t -= c;
			a[i] -= c;
			ret += 1ll * (cnt-i) * c;
		}
	}
	ret += x;
	return ret;
}

ll solve2() {
	int c = 0;
	ll ret = 1e18, cur = 0;
	int p1 = 1, p2 = cnt;
	for (int i = 1; i <= cnt; i++) val[i] = val[i-1] + a[i];
	for (int i = 1; i < cnt; i++) add(n + val[i], 1);
	while (p1 < p2) {
		// val 中的东西 - c 的绝对值之和
		ll res = 0;
		// > c 的
		res += (aski(2*n) - aski(n+c)) - 1ll * c * (ask(2*n) - ask(n+c));
		// <= c 的
		res += 1ll * c * ask(n+c) - aski(n+c);
		ret = min(ret, res + cur);
		while (p1 < p2 && a[p1] <= 0) {
			add(n+val[p1], -1);
			ll x = val[p1] - c;
			if (x < 0) cur -= x;
			else cur += x;
			++ p1;
		}
		while (p1 < p2 && a[p2] >= 0) {
			-- p2;
			add(n+val[p2], -1);
			ll x = val[p2] - c;
			if (x < 0) cur -= x;
			else cur += x;
		}
		if (p1 < p2) {
			++ c;
			cur += p1 - 1 + cnt - p2 + 1;
			-- a[p1], ++ a[p2];
		}
	}
	return ret;
}

int main() {
	memset(l, -1, sizeof(l));
	scanf("%d%d", &n, &m);
	if (n & 1) {
		puts("-1");
		return 0;
	}
	for (int i = 1; i <= m; i++) {
		int u, v; scanf("%d%d", &u, &v);
		addEdge(u, v); addEdge(v, u);
		++ deg[u], ++ deg[v];
	}
	if (m == n - 1) {
		int res = dfs(1, 0);
		if (res) puts("-1");
		else printf("%lld\n", cost);
		return 0;
	}
	queue<int> q;
	for (int i = 1; i <= n; i++) if (deg[i] == 1) q.push(i);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		for (int p = l[u]; p >= 0; p = E[p].x) {
			int v = E[p].v;
			-- deg[v];
			if (deg[v] == 1) {
				q.push(v);
			}
		}
	}
	for (int i = 1; i <= n; i++) if (deg[i] > 1) onc[i] = 1;
	for (int i = 1; i <= n; i++) {
		if (onc[i]) {
			s[i] = dfs(i, 0);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (onc[i]) {
			findcycle(i);
			break;
		}
	}
	for (int i = 1; i <= cnt; i += 2) a[i] = - a[i];
	int t = 0;
	for (int i = 1; i <= cnt; i++) t += a[i];
	if (cnt & 1) {
		if (t < 0) {
			for (int i = 1; i <= cnt; i++) a[i] = - a[i];
			t = -t;
		}
		cost += solve1(t / 2);
		for (int i = 1; i <= cnt; i++) val[i] = val[i-1] + a[i];
		for (int i = 1; i < cnt; i++) {
			if (val[i] < 0) cost -= val[i];
			else cost += val[i];
		}
	} else {
		if (t) {
			puts("-1");
			return 0;
		}
		ll res = 1e18;
		for (int i = 1; i <= cnt; i++) _a[i] = a[i];
		res = min(res, solve2());
		for (int i = 1; i <= cnt; i++) a[i] = -_a[i];
		res = min(res, solve2());
		cost += res;
	}
	printf("%lld\n", cost);
	return 0;
}

Measured memory_bytes: 9216