//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\
 
#include <bits/stdc++.h>
 
#define F first
#define S second
#define _sz(x) (int)x.size()
 
using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;
 
int const N = 1e5 + 20 ;
int n , m ;
vector <int> g[N] ;
 
struct edge {
	int u , v ;
	bool in ;
} e[N] ;
 
vector <int> vec ;
int d , ans , h[N] ;
bool vis[N] ;
 
int dfs (int v) {
	int d = 1 ;
	vis[v] = 1 ;
	for (int i : g[v]) {
		int u = e[i].u ^ e[i].v ^ v ;
		if (!vis[u]) {
			e[i].in = 1 ;
			h[u] = h[v] ^ 1 ;
			d -= dfs(u) ;
		}
	}
 
	vec.push_back(d) ;
	ans += abs(d) ;
 
	return d ;
}
 
int token[N] ;
int want = -1 ;
 
int get (int v , int par = -1) {
	int d = 0 ;
	if (h[v] != want) d ++ ;
	d -= token[v] ;
 
	for (int i : g[v]) {
		int u = e[i].u ^ e[i].v ^ v ;
 
		if (e[i].in && u != par) {
			d += get(u , v) ;
		}
	}
 
	ans += abs(d) ;
	return d ;
}
 
int main(){
	ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;
	
	cin >> n >> m ;
 
	for (int i = 0 ; i < m ; i ++) {
		cin >> e[i].u >> e[i].v ;
		e[i].u -- , e[i].v -- ;
 
		g[e[i].u].push_back(i) ;
		g[e[i].v].push_back(i) ;
	}
 
	d = dfs(0) ;
 
	if (m == n - 1) {
		if (!d) cout << ans << '\n' ;
		else cout << "-1\n" , 0 ;
		return 0 ;
	}
 
	bool odd_cycle = 0 ;
 
	for (int i = 0 ; i < m ; i ++)
		if (!e[i].in && h[e[i].u] == h[e[i].v]) odd_cycle = 1 ;
 
	if (odd_cycle) {
		if (d & 1) return cout << "-1\n" , 0 ;
 
		d /= 2 ;
 
		for (int i = 0 ; i < m ; i ++)
			if (!e[i].in) want = h[e[i].u] , token[e[i].u] = token[e[i].v] = (h[e[i].u] ? -d : d) ;
 
		for (int i = 0 ; i < n ; i ++)
			if (h[i] == want) token[i] ++ ;
 
		ans = abs(d) ;
		get(0) ;
		cout << ans << '\n' ;
	}
	else {
		if (d) return cout << "-1\n" , 0 ;
 
		assert(0) ;
 
		sort(vec.begin() , vec.end()) ;
 
		int x = vec[(n - 1) / 2] ;
		ans += x * (n - 1) + x ;
 
		cout << ans << '\n' ;
	}
}
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define F first
#define S second
#define _sz(x) (int)x.size()

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

int const N = 1e5 + 20 ;
int n , m ;
vector <int> g[N] ;

struct edge {
	int u , v ;
	bool in ;
} e[N] ;

vector <int> vec ;
int d , ans , h[N] ;
bool vis[N] ;

int dfs (int v) {
	int d = 1 ;
	vis[v] = 1 ;
	for (int i : g[v]) {
		int u = e[i].u ^ e[i].v ^ v ;
		if (!vis[u]) {
			e[i].in = 1 ;
			h[u] = h[v] ^ 1 ;
			d -= dfs(u) ;
		}
	}

	vec.push_back(d) ;
	ans += abs(d) ;

	return d ;
}

int token[N] ;
int want = -1 ;

int get (int v , int par = -1) {
	int d = 0 ;
	if (h[v] != want) d ++ ;
	d -= token[v] ;

	for (int i : g[v]) {
		int u = e[i].u ^ e[i].v ^ v ;

		if (e[i].in && u != par) {
			d += get(u , v) ;
		}
	}

	ans += abs(d) ;
	return d ;
}

int main(){
	ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ;
	
	cin >> n >> m ;

	for (int i = 0 ; i < m ; i ++) {
		cin >> e[i].u >> e[i].v ;
		e[i].u -- , e[i].v -- ;

		g[e[i].u].push_back(i) ;
		g[e[i].v].push_back(i) ;
	}

	d = dfs(0) ;

	if (m == n - 1) {
		if (!d) cout << ans << '\n' ;
		else cout << "-1\n" , 0 ;
		return 0 ;
	}

	bool odd_cycle = 0 ;

	for (int i = 0 ; i < m ; i ++)
		if (!e[i].in && h[e[i].u] == h[e[i].v]) odd_cycle = 1 ;

	if (odd_cycle) {
		if (d & 1) return cout << "-1\n" , 0 ;

		d /= 2 ;

		for (int i = 0 ; i < m ; i ++)
			if (!e[i].in) want = h[e[i].u] , token[e[i].u] = token[e[i].v] = -d ;

		for (int i = 0 ; i < n ; i ++)
			if (h[i] == want) token[i] ++ ;

		ans = abs(d) ;
		get(0) ;
		cout << ans << '\n' ;
	}
	else {
		if (d) return cout << "-1\n" , 0 ;

		assert(0) ;

		sort(vec.begin() , vec.end()) ;

		int x = vec[(n - 1) / 2] ;
		ans += x * (n - 1) + x ;

		cout << ans << '\n' ;
	}
}
