#include <bits/stdc++.h>
using namespace std;
const double PI = acos(-1.0);
const long long INF = 1000 * 1000 * 1000 + 7;
const long long LINF = INF * (long long)INF;
const int MAX = 100100;
vector<int> g[MAX];
int P[MAX];
int n;
int SZ[MAX];
int a, b;
int p;
void dfs(int x, int p, int c) {
  P[x] = p;
  SZ[x] += c;
  for (int i = (0); i < ((int)g[x].size()); i++) {
    int to = g[x][i];
    if (to == p) continue;
    if (x == a && to == b) continue;
    if (x == b && to == a) continue;
    dfs(to, x, -c);
    SZ[x] += SZ[to];
  }
}
long long solveTree() {
  dfs(0, -1, 1);
  long long res = 0;
  if (p == 1) {
    if (SZ[0] % 2 != 0) return -1;
    int cnt = SZ[0] / 2;
    for (int i = (0); i < (n); i++) {
      SZ[i] = 0;
    }
    SZ[a] -= cnt;
    SZ[b] -= cnt;
    res += abs(cnt);
    dfs(0, -1, 1);
  }
  if (SZ[0] != 0) return -1;
  for (int i = (1); i < (n); i++) {
    res += abs(SZ[i]);
  }
  return res;
}
int D[MAX];
int dfs2(int x, int p, int d) {
  D[x] = d;
  for (int i = (0); i < ((int)g[x].size()); i++) {
    int to = g[x][i];
    if (to == p) continue;
    if (D[to]) {
      a = x;
      b = to;
      if ((D[to] ^ d) & 1) return 0;
      return 1;
    }
    int val = dfs2(to, x, d + 1);
    if (val != -1) return val;
  }
  return -1;
}
long long calc(int m) {
  for (int i = (0); i < (n); i++) {
    SZ[i] = 0;
  }
  SZ[a] = m;
  SZ[b] = -m;
  return solveTree() + m;
}
int main() {
  int m;
  scanf("%d%d", &n, &m);
  for (int i = (0); i < (m); i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    x--;
    y--;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  if (m == n - 1) {
    cout << solveTree() << endl;
    return 0;
  }
  p = dfs2(0, -1, 1);
  if (p == 1) {
    cout << solveTree() << endl;
    return 0;
  }
  if (p == 0) {
    int l = -n - 4, r = n + 4;
    while (r - l > 4) {
      int m = (r - l) / 3;
      int m1 = l + m;
      int m2 = r - m;
      long long v1 = calc(m1);
      long long v2 = calc(m2);
      if (v1 < v2)
        r = m2;
      else
        l = m1;
    }
    long long res = LINF;
    while (l <= r) {
      res = min(res, calc(l));
      l++;
    }
    cout << res << endl;
    return 0;
  }
  throw -1;
}
