#include "bits/stdc++.h"
using namespace std;
#define int long long
vector<int> g[101010];
int color[101010];
int black_all, white_all, type, start, goal;
long long ans;
bool in_start[101010], in_goal[101010];
vector<int> flow;
int cnt_k;
void check(int v, int prev, int d) {
color[v] = d;
if (d & 1) black_all ++;
else white_all ++;
for (auto u : g[v]) if (u != prev) {
if (color[u] == -1) {
check(u, v, 1 - d);
} else {
start = v;
goal = u;
if (color[u] == 1 - d) {
type = 1;
} else {
type = 2;
}
}
}
}
pair<int, int> dfs(int v, int prev, int d) {
int black = 0, white = 0;
for (auto u : g[v]) if (u != prev) {
pair<int, int> get = dfs(u, v, d + 1);
black += get.first;
white += get.second;
}
if (d & 1) black ++;
else white ++;
ans += abs(black - white);
return make_pair(black, white);
}
pair<int, int> dfs2(int v, int prev, int d) {
int black = 0, white = 0;
in_start[v] = false, in_goal[v] = false;
if (v == start) in_start[v] = true;
if (v == goal) in_goal[v] = true;
for (auto u : g[v]) if (u != prev) {
pair<int, int> get = dfs2(u, v, d + 1);
in_start[v] |= in_start[u];
in_goal[v] |= in_goal[u];
black += get.first;
white += get.second;
}
if (d & 1) black ++;
else white ++;
if ((in_start[v] && in_goal[v]) || (!in_start[v] && !in_goal[v])) {
ans += abs(black - white);
} else {
flow.push_back(black - white);
}
return make_pair(black, white);
}
pair<int, int> dfs3(int v, int prev, int d) {
int black = 0, white = 0;
for (auto u : g[v]) if (u != prev) {
pair<int, int> get = dfs3(u, v, d + 1);
black += get.first;
white += get.second;
}
if (d & 1) black ++;
else white ++;
if (v == start || v == goal) black -= cnt_k;
ans += abs(black - white);
return make_pair(black, white);
}
signed main() {
int n, m;
scanf("%lld%lld", &n, &m);
for (int i = 0; i < m; i ++) {
int a, b;
scanf("%lld%lld", &a, &b);
a --, b --;
g[a].push_back(b);
g[b].push_back(a);
}
type = 0;
memset(color, -1, sizeof color);
check(0, -1, 0);
if (type == 0 || type == 1) {
if (black_all != white_all) {
puts("-1");
return 0;
}
}
if (type == 2) {
if (black_all % 2 != white_all % 2) {
puts("-1");
return 0;
}
}
if (type == 0) {
dfs(0, -1, 0);
printf("%lld\n", ans);
return 0;
}
g[start].erase(remove(g[start].begin(), g[start].end(), goal), g[start].end());
g[goal].erase(remove(g[goal].begin(), g[goal].end(), start), g[goal].end());
// for (int i = 0; i < g[start].size(); i ++) {
// if (g[start][i] == goal) {
// g[start].erase(g[start].begin() + i);
// }
// }
// for (int i = 0; i < g[goal].size(); i ++) {
// if (g[goal][i] == start) {
// g[goal].erase(g[goal].begin() + i);
// }
// }
if (type == 1) {
dfs2(0, -1, 0);
int lb = -101010, ub = 101010;
int cnt = 0;
while (ub - lb > 0) {
cnt ++;
if (cnt > 100) break;
int left = (lb * 2 + ub) / 3;
int right = (lb + ub * 2) / 3;
int left_ans = 0, right_ans = 0;
for (auto f : flow) {
left_ans += abs(left + f);
right_ans += abs(right + f);
}
if (left_ans < right_ans) ub = right;
else lb = left;
}
int res = 0x3f3f3f3f;
for (int i = lb - 10; i < lb + 10; i ++) {
int sum = 0;
for (auto f : flow) {
sum += abs(i + f);
}
sum += abs(i); //self
res = min(res, sum);
}
ans += res;
printf("%lld\n", ans);
return 0;
}
if (type == 2) {
cnt_k = (black_all - white_all) / 2;
dfs3(0, -1, 0);
ans += abs(cnt_k);
printf("%lld\n", ans);
}
return 0;
}