#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#define cmin(a,b) (a>(b)?a=(b),1:0)
#define cmax(a,b) (a<(b)?a=(b),1:0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
namespace io
{
	int F()
	{
		int n=0,F=1;
		char ch;
		while((ch=getchar())!='-'&&(ch<'0'||ch>'9'));
		ch=='-'?F=0:n=ch-'0';
		while((ch=getchar())>='0'&&ch<='9')n=n*10+ch-'0';
		return F?n:-n;
	}
}
struct edge
{
	int to;
	int next;
}e[333333];
int pe=111111;
int deg[111111];
void insert(int a,int to)
{
	e[pe]=(edge){to,e[a].next};
	e[a].next=pe++;
	++deg[to];
}
int siz[111111][2];
int c[111111];
int q[111111],hq,tq;
int cyc[111111];
long long ans;
void dfs(int o,int fa)
{
	siz[o][c[o]]=1,siz[o][!c[o]]=0;
	for(register int p=e[o].next;p;p=e[p].next)
		if(e[p].to!=fa)
		{
			c[e[p].to]=!c[o];
			dfs(e[p].to,o);
			siz[o][0]+=siz[e[p].to][0];
			siz[o][1]+=siz[e[p].to][1];
		}
	int d=dmin(siz[o][0],siz[o][1]);
	siz[o][0]-=d,siz[o][1]-=d;
	ans+=siz[o][0]+siz[o][1];
}
int pv,cnt[222222][2],d[222222][2];
void dfs2(int o,int fa)
{
	siz[o][0]=1;
	siz[o][1]=0;
	for(register int p=e[o].next;p;p=e[p].next)
		if(e[p].to!=fa&&!cyc[e[p].to])
		{
			dfs2(e[p].to,o);
			siz[o][0]+=siz[e[p].to][1];
			siz[o][1]+=siz[e[p].to][0];
		}
	int d=dmin(siz[o][0],siz[o][1]);
	siz[o][0]-=d,siz[o][1]-=d;
	ans+=siz[o][0]+siz[o][1];
}
void dfs3(int o,int fa,int top)
{
	dfs2(o,o);
	++pv;
	cnt[pv][0]=siz[o][0];
	cnt[pv][1]=siz[o][1];
	ans-=siz[o][0]+siz[o][1];
	for(register int p=e[o].next;p;p=e[p].next)
		if(e[p].to!=fa&&e[p].to!=top&&cyc[e[p].to])
		{
			dfs3(e[p].to,o,top);
			return;
		}
}
#define ab(x) ((x)>0?(x):-(x))
int main()
{
	//freopen("reverse.in","r",stdin);
	//freopen("reverse.out","w",stdout);
	//int T=io::F();
	//while(T--)
	{
		pe=111111;
		for(register int i=1;i<=pe;++i)e[i].next=0;
		memset(deg,0,sizeof(deg));
		int n=io::F(),m=io::F();
		for(register int i=1;i<=m;++i)
		{
			int x=io::F(),y=io::F();
			insert(x,y);
			insert(y,x);
		}
		if(n&1){puts("-1");return 0;}
		if(m==n-1)
		{
			ans=0;
			dfs(1,1);
			if(siz[1][0]||siz[1][1]){puts("-1");return 0;}
			printf("%lld\n",ans);
			return 0;
		}
		else
		{
			int md=0;
			for(register int i=1;i<=n;++i)cmax(md,deg[i]);
			if(md==2){printf("%d\n",n/2);return 0;}
			hq=tq=1;
			for(register int i=1;i<=n;++i)
				if(deg[i]==1)q[tq++]=i,cyc[i]=0;
					else cyc[i]=1;
			for(;hq!=tq;++hq)
				for(register int p=e[q[hq]].next;p;p=e[p].next)
					if(--deg[e[p].to]==1)q[tq++]=e[p].to,cyc[e[p].to]=0;
			ans=0;
			pv=0;
			for(register int i=1;i<=n;++i)
				if(cyc[i]){dfs3(i,i,i);break;}
			int sum=0;
			for(register int i=1;i<=pv;++i)
				sum+=cnt[i][0]+cnt[i][1];//cnt[pv+i][0]=cnt[i][0],cnt[pv+i][1]=cnt[i][1];
			sum/=2;
			if((long long)sum*4*pv>=200000000)sum=50000000/pv;
			long long rr=0x3f3f3f3f3f3f3f3fll;
			for(register int i=0;i<=sum;++i)
			{
				long long tmp=ab(i);
				for(register int j=1;j<=pv;++j)d[j][0]=cnt[j][0],d[j][1]=cnt[j][1];
				d[pv][0]-=i,d[1][1]+=i;
				for(register int j=1;j<pv;++j)
				{
					int min=dmin(d[j][0],d[j][1]);
					d[j][0]-=min;
					d[j][1]-=min;
					tmp+=ab(d[j][0]+d[j][1]);
					d[j+1][0]+=d[j][1];
					d[j+1][1]+=d[j][0];
				}
				if(d[pv][0]==d[pv][1])cmin(rr,tmp);
			}
			for(register int i=0;i<=sum;++i)
			{
				long long tmp=ab(i);
				for(register int j=1;j<=pv+1;++j)d[j][0]=cnt[j][0],d[j][1]=cnt[j][1];
				d[pv][1]-=i,d[1][0]+=i;
				for(register int j=1;j<pv;++j)
				{
					int min=dmin(d[j][0],d[j][1]);
					d[j][0]-=min;
					d[j][1]-=min;
					tmp+=ab(d[j][0]+d[j][1]);
					d[j+1][0]+=d[j][1];
					d[j+1][1]+=d[j][0];
				}
				if(d[pv][0]==d[pv][1])cmin(rr,tmp);
			}
			for(register int i=0;i<=sum;++i)
			{
				long long tmp=ab(i);
				for(register int j=1;j<=pv;++j)d[j][0]=cnt[j][0],d[j][1]=cnt[j][1];
				d[pv][0]+=i,d[1][1]-=i;
				for(register int j=pv;j>1;--j)
				{
					int min=dmin(d[j][0],d[j][1]);
					d[j][0]-=min;
					d[j][1]-=min;
					tmp+=ab(d[j][0]+d[j][1]);
					d[j-1][0]+=d[j][1];
					d[j-1][1]+=d[j][0];
				}
				if(d[1][0]==d[1][1])cmin(rr,tmp);
			}
			for(register int i=0;i<=sum;++i)
			{
				long long tmp=ab(i);
				for(register int j=1;j<=pv;++j)d[j][0]=cnt[j][0],d[j][1]=cnt[j][1];
				d[pv][1]+=i,d[1][0]-=i;
				for(register int j=pv;j>1;--j)
				{
					int min=dmin(d[j][0],d[j][1]);
					d[j][0]-=min;
					d[j][1]-=min;
					tmp+=ab(d[j][0]+d[j][1]);
					d[j-1][0]+=d[j][1];
					d[j-1][1]+=d[j][0];
				}
				if(d[1][0]==d[1][1])cmin(rr,tmp);
			}
			if(rr==0x3f3f3f3f3f3f3f3fll)puts("-1");
				else printf("%lld\n",ans+rr);
		}
	}
	return 0;
}