#include <bits/stdc++.h>
using namespace std;
struct edge {
  int x, y, f, next;
} a[100010 * 2];
int n, m, l, p[100010], x, y, def[100010], sum[100010], w[100010], fa[100010],
    cl, d[100010], flag[100010], b[100010], now, L, R, mid, s1, z;
long long f_tree[100010], ans, s[100010], ans1;
inline void add(int x, int y) {
  a[++l].x = x;
  a[l].y = y;
  a[l].f = 0;
  a[l].next = p[x];
  p[x] = l;
}
inline void dp_tree(int x, int fa) {
  for (int i = p[x]; i; i = a[i].next)
    if (fa != a[i].y && !flag[a[i].y]) {
      def[a[i].y] = def[x] + 1;
      dp_tree(a[i].y, x);
    }
  f_tree[x] = 0;
  int s1 = 0, s2 = 0;
  for (int i = p[x]; i; i = a[i].next)
    if (fa != a[i].y && !flag[a[i].y]) {
      f_tree[x] += f_tree[a[i].y];
      if (sum[a[i].y] <= 0)
        s2 += -sum[a[i].y];
      else
        s1 += sum[a[i].y];
    }
  f_tree[x] += 2 * min(s1, s2) + max(s1 - s2, s2 - s1);
  sum[x] = s1 - s2;
  if (def[x] & 1)
    sum[x] += w[x];
  else
    sum[x] -= w[x];
}
inline void dp(int x, int fa) {
  for (int i = p[x]; i; i = a[i].next)
    if (fa != a[i].y && !a[i].f) dp(a[i].y, x);
  f_tree[x] = 0;
  int s1 = 0, s2 = 0;
  for (int i = p[x]; i; i = a[i].next)
    if (fa != a[i].y && !a[i].f) {
      f_tree[x] += f_tree[a[i].y];
      if (sum[a[i].y] <= 0)
        s2 += -sum[a[i].y];
      else
        s1 += sum[a[i].y];
    }
  f_tree[x] += 2 * min(s1, s2) + max(s1 - s2, s2 - s1);
  sum[x] = s1 - s2;
  sum[x] += w[x];
}
inline void dfs_tree(int x, int fa) {
  for (int i = p[x]; i; i = a[i].next)
    if (fa != a[i].y && !a[i].f) {
      def[a[i].y] = def[x] + 1;
      dfs_tree(a[i].y, x);
    }
}
inline void dfs_circle(int x) {
  flag[x] = 1;
  for (int i = p[x]; i; i = a[i].next)
    if (!a[i].f) {
      if (flag[a[i].y]) {
        cl = 1;
        d[0] = x;
        d[1] = a[i].y;
      } else {
        a[i].f = a[i ^ 1].f = 1;
        fa[a[i].y] = x;
        dfs_circle(a[i].y);
      }
    }
}
int main() {
  scanf("%d%d", &n, &m);
  l = 1;
  memset(p, 0, sizeof(p));
  for (int i = 1; i <= m; i++) {
    scanf("%d%d", &x, &y);
    add(x, y);
    add(y, x);
  }
  if (m == n - 1) {
    memset(flag, 0, sizeof(flag));
    for (int i = 1; i <= n; i++) w[i] = 1;
    def[1] = 1;
    dp_tree(1, 0);
    if (sum[1])
      printf("-1");
    else
      printf("%lld", f_tree[1]);
    return 0;
  }
  if (m == n) {
    memset(flag, 0, sizeof(flag));
    fa[1] = 0;
    dfs_circle(1);
    while (d[cl] != d[0]) {
      cl++;
      d[cl] = fa[d[cl - 1]];
    }
  }
  for (int i = 2; i <= l; i++) a[i].f = 0;
  memset(flag, 0, sizeof(flag));
  if (!(cl & 1)) {
    return 1;
    for (int i = 1; i <= cl; i++) flag[d[i]] = 1;
    ans1 = 0;
    for (int i = 1; i <= cl; i++) {
      def[d[i]] = i & 1;
      w[d[i]] = 1;
      dp_tree(d[i], 0);
      ans1 += f_tree[d[i]];
    }
    b[0] = 0;
    for (int i = 1; i <= cl; i++) b[i] = b[i - 1] + sum[d[i]];
    if (b[cl]) {
      printf("-1");
      return 0;
    }
    sort(b + 1, b + 1 + cl);
    s[0] = 0;
    for (int i = 1; i <= cl; i++) s[i] = s[i - 1] + b[i];
    now = 0;
    ans = 1000000000000000000LL;
    for (int i = 1; i <= cl; i++) {
      now += sum[d[i]];
      if (b[1] - now > 0)
        L = 0;
      else {
        L = 1;
        R = cl;
        while (L < R) {
          mid = (L + R) >> 1;
          if (L == R - 1) mid++;
          if (b[mid] - now <= 0)
            L = mid;
          else
            R = mid - 1;
        }
      }
      ans = min(ans, (long long)now * L - s[L] + s[cl] - s[L] -
                         (long long)now * (cl - L));
    }
    printf("%lld\n", ans + ans1);
    return 0;
  }
  if (cl & 1) {
    if (n & 1) {
      printf("-1");
      return 0;
    }
    x = d[1];
    y = d[2];
    for (int i = p[x]; i; i = a[i].next)
      if (a[i].y == y) a[i].f = a[i ^ 1].f = 1;
    def[1] = 1;
    dfs_tree(1, 0);
    s1 = 0;
    for (int i = 1; i <= n; i++)
      if (def[i] & 1) s1++;
    if (s1 * 2 >= n) {
      for (int i = 1; i <= n; i++) def[i] ^= 1;
      s1 = n - s1;
    }
    z = (n - s1 * 2) >> 1;
    ans = z;
    for (int i = 1; i <= n; i++) w[i] = def[i] & 1 ? 1 : -1;
    w[x] += z;
    w[y] += z;
    dp(1, 0);
    ans += f_tree[1];
    printf("%lld", ans);
    return 0;
  }
  return 0;
}
