#include<cstdio>
#include<algorithm>
const int MaxN=100010;
int N,M,a[MaxN],b[MaxN];
namespace bf{
	int Q[1<<20],D[1<<20];
	int solve(){
		for(int s=0;s<1<<N;s++)D[s]=-1;
		int*h=Q,*t=Q+1;D[*h=0]=0;
		for(;h<t;h++){
			for(int i=0;i<M;i++)if((*h>>a[i]-1&1)==(*h>>b[i]-1&1)){
				int x=*h^1<<a[i]-1^1<<b[i]-1;
				if(D[x]<0)D[*t++=x]=D[*h]+1;
			}
		}
		return D[(1<<N)-1];
	}
}
namespace tree{
	struct edge{int to;edge*next;}E[MaxN*2],*ne,*fir[MaxN];
	int deg[MaxN];
	void link(int u,int v){*ne=(edge){v,fir[u]};fir[u]=ne++;deg[u]++;}
	int S[MaxN],f[MaxN],C[MaxN];
	long long list[MaxN];
	long long solve(){
		ne=E;
		for(int i=1;i<=N;i++)fir[i]=0,deg[i]=0,f[i]=1;
		for(int i=0;i<M;i++)link(a[i],b[i]),link(b[i],a[i]);
		if(M<N)deg[1]+=2;
		int*t=S;
		for(int i=1;i<=N;i++)deg[i]==1?*++t=i:1;
		long long s=0;
		while(t>S){
			int x=*t--;
			deg[x]=0;
			for(edge*e=fir[x];e;e=e->next)if(deg[e->to]){
				f[e->to]-=f[x];
				if(--deg[e->to]==1)*++t=e->to;
			}
			s+=f[x]>0?f[x]:-f[x];
		}
		if(M<N)return f[1]?-1:s;
		int len=0,x=1;
		while(!deg[x])++x;
		while(deg[x]){
			C[len++]=f[x];
			deg[x]=0;
			for(edge*e=fir[x];e;e=e->next){
				if(deg[e->to]){x=e->to;break;}
			}
		}
		if(len<2)return*C?-1:s;
		for(int i=*list=0;i<len;i++)list[i+1]=list[i]+(i&1?-C[i]:C[i]);
		if(len%2==0){
			if(list[len])return-1;
			std::nth_element(list,list+len/2,list+len);
			for(int i=0;i<len;i++)i<len/2?s-=list[i]:s+=list[i];
		}
		else{
			if(list[len]%2)return-1;
			long long u=list[len]/2;
			for(int i=0;i<len;i++){
				s+=u>0?u:-u;
				u=C[i]-u;
			}
		}
		return s;
	}
}
int main(){
	//freopen("in.txt","r",stdin);
	while(scanf("%d%d",&N,&M)==2){
		for(int i=0;i<M;i++)scanf("%d%d",a+i,b+i);
		long long ans=tree::solve();
		printf("%lld\n",ans);
		/*
		if(ans1!=ans2){
			printf("%d %d\n",N,M);
			for(int i=0;i<M;i++)printf("%d %d\n",a[i],b[i]);
			return puts("WA"),0;
		}
		*/
	}
	//puts("OK");
}