#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 100010
#define inf 1000000000000000000LL
#define ll long long
using namespace std;

struct edge{int x, y, f, next;}a[N*2];
int n, m, l, p[N], x, y, def[N], sum[N], w[N], fa[N], cl, d[N], flag[N], b[N], now, L, R, mid, s1, z;
ll f_tree[N], ans, s[N], ans1;

inline void add(int x, int y){a[++l].x=x; a[l].y=y; a[l].f=0; a[l].next=p[x]; p[x]=l;}

inline void dp_tree(int x, int fa){
	for(int i=p[x]; i; i=a[i].next)if(fa!=a[i].y&&!flag[a[i].y]){
		def[a[i].y]=def[x]+1; dp_tree(a[i].y, x);
	}
	f_tree[x]=0; int s1=0, s2=0;
	for(int i=p[x]; i; i=a[i].next)if(fa!=a[i].y&&!flag[a[i].y]){
		f_tree[x]+=f_tree[a[i].y];
		if(sum[a[i].y]<=0)s2+=-sum[a[i].y]; else s1+=sum[a[i].y];
	}
	f_tree[x]+=2*min(s1, s2)+max(s1-s2, s2-s1);
	sum[x]=s1-s2; if(def[x]&1)sum[x]+=w[x]; else sum[x]-=w[x];
}
inline void dp(int x, int fa){
	for(int i=p[x]; i; i=a[i].next)if(fa!=a[i].y&&!a[i].f)dp(a[i].y, x);
	f_tree[x]=0; int s1=0, s2=0;
	for(int i=p[x]; i; i=a[i].next)if(fa!=a[i].y&&!a[i].f){
		f_tree[x]+=f_tree[a[i].y];
		if(sum[a[i].y]<=0)s2+=-sum[a[i].y]; else s1+=sum[a[i].y];
	}
	f_tree[x]+=2*min(s1, s2)+max(s1-s2, s2-s1);
	sum[x]=s1-s2; sum[x]+=w[x];
}
inline void dfs_tree(int x, int fa){
	for(int i=p[x]; i; i=a[i].next)if(fa!=a[i].y&&!a[i].f){
		def[a[i].y]=def[x]+1; dfs_tree(a[i].y, x);
	}
}
inline void dfs_circle(int x){
	flag[x]=1;
	for(int i=p[x]; i; i=a[i].next)if(!a[i].f){
		if(flag[a[i].y]){cl=1; d[0]=x; d[1]=a[i].y;}
		else{a[i].f=a[i^1].f=1; fa[a[i].y]=x; dfs_circle(a[i].y);}
	}
}

int main(){
	scanf("%d%d", &n, &m);
	l=1; memset(p, 0, sizeof(p));
	for(int i=1; i<=m; i++){scanf("%d%d", &x, &y); add(x, y); add(y, x);}
	//tree
	if(m==n-1){
		memset(flag, 0, sizeof(flag));
		for(int i=1; i<=n; i++)w[i]=1;
		def[1]=1; dp_tree(1, 0);
		if(sum[1])printf("-1"); else printf("%lld", f_tree[1]);
		return 0;
	}
	if(m==n){
		memset(flag, 0, sizeof(flag));
		fa[1]=0; dfs_circle(1);
		while(d[cl]!=d[0]){cl++; d[cl]=fa[d[cl-1]];}
	}
	for(int i=2; i<=l; i++)a[i].f=0;
	memset(flag, 0, sizeof(flag));
	//even_cycle
	if(!(cl&1)){
		for(int i=1; i<=cl; i++)flag[d[i]]=1;
		for(int i=1; i<=n; i++)w[i]=1;
		ans1=0;
		for(int i=1; i<=cl; i++){
			def[d[i]]=i&1; dp_tree(d[i], 0);
			ans1+=f_tree[d[i]];
		}
		b[0]=0; for(int i=1; i<=cl; i++)b[i]=b[i-1]+sum[d[i]];
		if(b[cl]){printf("-1"); return 0;}
		sort(b+1, b+1+cl);
		s[0]=0; for(int i=1; i<=cl; i++)s[i]=s[i-1]+b[i]; now=0;
		ans=inf;
		for(int i=1; i<=cl; i++){
			now+=sum[d[i]];
			if(b[1]-now>0)L=0;
			else{
				L=1; R=cl;
				while(L<R){
					mid=(L+R)>>1; if(L==R-1)mid++;
					if(b[mid]-now<=0)L=mid; else R=mid-1;
				}
			}
			ans=min(ans, (ll)now*L-s[L]+s[cl]-s[L]-(ll)now*(cl-L));
		}
		printf("%lld\n", ans+ans1);
		return 0;
	}
	//odd_cycle
	if(cl&1){
		if(n&1){printf("-1"); return 0;}
		x=d[1]; y=d[2];
		for(int i=p[x]; i; i=a[i].next)if(a[i].y==y)a[i].f=a[i^1].f=1;
		def[1]=1; dfs_tree(1, 0);
		s1=0; for(int i=1; i<=n; i++)if(def[i]&1)s1++;
		if(s1*2>=n){for(int i=1; i<=n; i++)def[i]^=1; s1=n-s1;}
		z=(n-s1*2)>>1; ans=z;
		for(int i=1; i<=n; i++)w[i]=def[i]&1?1:-1; w[x]+=z; w[y]+=z;
		dp(1, 0); ans+=f_tree[1];
		printf("%lld", ans);
		return 0;
	}
	return 0;
}

Measured memory_bytes: 9600