#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
struct node {
    int to,next;
}E[MAXN * 2];
int N,head[MAXN],sumE,M,fa[MAXN],dep[MAXN],st,ed;
int64 dp[MAXN][2],ans,pre[MAXN],suf[MAXN],prez[MAXN][2],sufz[MAXN][2];
bool vis[MAXN];
int c[MAXN],tot;
int sta[MAXN],top,num[MAXN];
void add(int u,int v) {
    E[++sumE].to = v;
    E[sumE].next = head[u];
    head[u] = sumE;
}
void dfs(int u) {
    dp[u][0] = 1;
    for(int i = head[u] ; i ; i = E[i].next) {
	int v = E[i].to;
	if(v != fa[u]) {
	    fa[v] = u;
	    dfs(v);
	    ans += dp[v][0] + dp[v][1];
	    dp[u][0] += dp[v][1];
	    dp[u][1] += dp[v][0];
	}
    }
    int t = min(dp[u][0],dp[u][1]);
    dp[u][0] -= t;dp[u][1] -= t;
}
void find_circle(int u) {
    dep[u] = dep[fa[u]] + 1;
    vis[u] = 1;
    for(int i = head[u] ; i ; i = E[i].next) {
	int v = E[i].to;
	if(!vis[v]) {
	    fa[v] = u;
	    find_circle(v);
	}
	else if(dep[v] < dep[u]) {
	    st = u;ed = v;
	}
    }
}
void Calc(int u) {
    dp[u][0] = 1;
    vis[u] = 1;
    for(int i = head[u] ; i ; i = E[i].next) {
	int v = E[i].to;
	if(!vis[v]) {
	    Calc(v);
	    ans += dp[v][0] + dp[v][1];
	    dp[u][0] += dp[v][1];
	    dp[u][1] += dp[v][0];
	}
    }
    int t = min(dp[u][0],dp[u][1]);
    dp[u][0] -= t;
    dp[u][1] -= t;
}
void Solve() {
    read(N);read(M);
    int a,b;
    for(int i = 1 ; i <= M ; ++i) {
	read(a);read(b);
	add(a,b);add(b,a);
    }
    if(N & 1) {puts("-1");return;}
    if(M == N - 1) {
	dfs(1);
	if(dp[1][0] || dp[1][1]) {puts("-1");return;}
	out(ans);enter;
    }
    else {
	find_circle(1);
	int p = st;
	while(1) {
	    c[++tot] = p;
	    if(p == ed) break;
	    p = fa[p];
	}
	memset(vis,0,sizeof(vis));
	for(int i = 1 ; i <= tot ; ++i) vis[c[i]] = 1;
	for(int i = 1 ; i <= tot ; ++i) {
	    Calc(c[i]);
	}
	top = 0;
	for(int i = 1 ; i <= tot ; ++i) {
	    int u = c[i];
	    pre[i] = pre[i - 1];
	    if(dp[u][0] || dp[u][1]) {
		pre[i] += (i - 1) * (dp[u][0]+dp[u][1]);
	    }
	    for(int k = 0 ; k <= 1 ; ++k) {
		int t = k ^ ((i - 1) & 1);
		int cnt = dp[u][k];
		while(cnt && top && num[top] == t ^ 1) {
		    pre[i] -= sta[top] * 2;
		    --top;--cnt;
		}
		if(cnt) {
		    for(int j = 1 ; j <= cnt ; ++j) {
			sta[++top] = i - 1;num[top] = t;
		    }
		}
	    }
	    if(top) prez[i][num[top]] = top; 
	}
	top = 0;
	for(int i = tot ; i >= 1 ; --i) {
	    int u = c[i];
	    suf[i] = suf[i + 1];
	    if(dp[u][0] || dp[u][1]) {
		suf[i] += (tot - i) * (dp[u][0] + dp[u][1]);
	    }
	    for(int k = 0 ; k <= 1 ; ++k) {
		int t = k ^ ((tot - i) & 1);
		int cnt = dp[u][k];
		while(cnt && top && num[top] == t ^ 1) {
		    suf[i] -= sta[top] * 2;
		    --top;--cnt;
		}
		if(cnt) {
		    for(int j = 1 ; j <= cnt ; ++j) {sta[++top] = tot - i;num[top] = t;}
		}
	    }
	    if(top) sufz[i][num[top]] = top;
	}
	if(tot % 2 == 0) {
	    int64 res = 1e18;
	    for(int i = 1 ; i <= tot ; ++i) {
		if(prez[i][0] == sufz[i + 1][0] && prez[i][1] == sufz[i + 1][1]) {
		    res = min(res,pre[i] + suf[i + 1] + prez[i][0] + prez[i][1]);
		}
	    }
	    if(res >= 1e18) {
		puts("-1");
	    }
	    else {out(ans + res);enter;}
	}
	else {
	    int64 a = 1;
	    for(int64 i = 1 ; i <= 1e18LL ; ++i) a <<= 1LL;
	    out(a);enter;
	}
    }
}

int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}
