#include <bits/stdc++.h>
int N, M, head[100001], next[200001], to[200001], E, q[100001], fa[100001],
    dep[100001], fe[100001], v[100001], size[100001][2], cir[100001], L,
    oncir[100001];
inline void add(int u, int v) {
  next[++E] = head[u], to[E] = v, head[u] = E;
  next[++E] = head[v], to[E] = u, head[v] = E;
}
void Tree() {
  int H = 0, T = 1, u;
  q[1] = 1;
  while (H < T)
    for (int e = head[u = q[++H]]; e; e = next[e])
      if (to[e] != fa[u]) {
        fa[q[++T] = to[e]] = u;
        dep[to[e]] = dep[u] + 1;
      }
  for (int i = N; i; i--) {
    int u = q[i];
    size[u][dep[u] & 1] = 1;
    for (int e = head[u]; e; e = next[e])
      if (to[e] != fa[u]) {
        size[u][0] += size[to[e]][0];
        size[u][1] += size[to[e]][1];
      }
  }
  if (size[1][0] != size[1][1])
    puts("-1");
  else {
    long long O = 0;
    for (int i = 2; i <= N; i++)
      O += std::max(size[i][0] - size[i][1], size[i][1] - size[i][0]);
    printf("%lld\n", O);
  }
}
int S[100001][2], TL[262144][2][2], TR[262144][2][2];
void build(int p, int l, int r) {
  if (l == r) {
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) {
        TL[p][i][j] = 1000000000;
        TR[p][i][j] = -1000000000;
      }
    for (int i = 0; i < 2; i++)
      if (S[l][i]) TL[p][i][l & 1] = TR[p][i][l & 1] = l;
    return;
  }
  int m = l + r >> 1;
  build(p << 1, l, m);
  build(p << 1 | 1, m + 1, r);
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) {
      TL[p][i][j] = std::min(TL[p << 1][i][j], TL[p << 1 | 1][i][j]);
      TR[p][i][j] = std::max(TR[p << 1][i][j], TR[p << 1 | 1][i][j]);
    }
}
void update(int x) {
  int p = 1, l = 1, r = L;
  while (l < r) {
    int m = l + r >> 1;
    if (x <= m)
      p <<= 1, r = m;
    else
      p = p << 1 | 1, l = m + 1;
  }
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++) {
      TL[p][i][j] = 1000000000;
      TR[p][i][j] = -1000000000;
    }
  for (int i = 0; i < 2; i++)
    if (S[l][i]) TL[p][i][l & 1] = TR[p][i][l & 1] = l;
  while (p > 1) {
    p >>= 1;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 2; j++) {
        TL[p][i][j] = std::min(TL[p << 1][i][j], TL[p << 1 | 1][i][j]);
        TR[p][i][j] = std::max(TR[p << 1][i][j], TR[p << 1 | 1][i][j]);
      }
  }
}
std::pair<int, int> G(int p, int l, int r, int L, int R, int x, int y) {
  if (L <= l && r <= R) return {TL[p][x][y], TR[p][x][y]};
  int m = l + r >> 1;
  std::pair<int, int> GL = L <= m ? G(p << 1, l, m, L, R, x, y)
                                  : std::make_pair(1000000000, -1000000000),
                      GR = R > m ? G(p << 1 | 1, m + 1, r, L, R, x, y)
                                 : std::make_pair(1000000000, -1000000000);
  return {std::min(GL.first, GR.first), std::max(GL.second, GR.second)};
}
std::pair<int, std::pair<int, int> > Get(int x, int y) {
  std::pair<int, int> _L =
      std::max(std::make_pair(G(1, 1, L, 1, x, y, (x & 1) ^ 1).second, y),
               std::make_pair(G(1, 1, L, 1, x, y ^ 1, x & 1).second, y ^ 1));
  std::pair<int, int> __L = std::max(
      std::make_pair(G(1, 1, L, x, L, y, ((x ^ L) & 1) ^ 1).second, y),
      std::make_pair(G(1, 1, L, x, L, y ^ 1, (x ^ L) & 1).second, y ^ 1));
  std::pair<int, int> _R =
      std::min(std::make_pair(G(1, 1, L, x, L, y, (x & 1) ^ 1).first, y),
               std::make_pair(G(1, 1, L, x, L, y ^ 1, x & 1).first, y ^ 1));
  std::pair<int, int> __R = std::min(
      std::make_pair(G(1, 1, L, 1, x, y, ((x ^ L) & 1) ^ 1).first, y),
      std::make_pair(G(1, 1, L, 1, x, y ^ 1, (x ^ L) & 1).first, y ^ 1));
  std::pair<int, std::pair<int, int> > U_L = {x - _L.first, _L},
                                       U__L = {x - __L.first + L, __L},
                                       U_R = {_R.first - x, _R},
                                       U__R = {__R.first - x + L, __R};
  return std::min(std::min(U_L, U__L), std::min(U_R, U__R));
}
void Circle() {
  int H = 0, T = 1, u, MU = 0, MV = 0;
  q[1] = 1;
  v[1] = 1;
  while (H < T)
    for (int e = head[u = q[++H]]; e; e = next[e])
      if (e != ((fe[u] + 1) ^ 1) - 1) {
        if (v[to[e]]) {
          if (e & 1) {
            MU = u;
            MV = to[e];
          }
        } else {
          fa[q[++T] = to[e]] = u;
          fe[to[e]] = e;
          dep[to[e]] = dep[u] + 1;
          v[to[e]] = 1;
        }
      }
  static int LH[100001], RH[100001], LN, RN;
  while (dep[MU] > dep[MV]) {
    LH[++LN] = MU;
    MU = fa[MU];
  }
  while (dep[MU] < dep[MV]) {
    RH[++RN] = MV;
    MV = fa[MV];
  }
  while (MU != MV) {
    LH[++LN] = MU;
    MU = fa[MU];
    RH[++RN] = MV;
    MV = fa[MV];
  }
  LH[++LN] = MU;
  std::reverse(RH + 1, RH + RN + 1);
  std::copy(LH + 1, LH + LN + 1, cir + 1);
  std::copy(RH + 1, RH + RN + 1, cir + LN + 1);
  L = LN + RN;
  for (int i = 1; i <= L; i++) oncir[cir[i]] = i;
  long long O = 0;
  for (int i = 1; i <= L; i++) {
    H = 0, T = 1;
    q[1] = cir[i];
    fa[cir[i]] = 0;
    dep[cir[i]] = 0;
    while (H < T)
      for (int e = head[u = q[++H]]; e; e = next[e])
        if (!oncir[to[e]] && to[e] != fa[u]) {
          fa[q[++T] = to[e]] = u;
          dep[to[e]] = dep[u] + 1;
        }
    for (int i = T; i; i--) {
      int u = q[i];
      size[u][dep[u] & 1] = 1;
      for (int e = head[u]; e; e = next[e])
        if (!oncir[to[e]] && to[e] != fa[u]) {
          size[u][0] += size[to[e]][0];
          size[u][1] += size[to[e]][1];
        }
    }
    for (int i = 2; i <= T; i++)
      O += std::max(size[q[i]][0] - size[q[i]][1],
                    size[q[i]][1] - size[q[i]][0]);
  }
  for (int i = 1; i <= L; i++) {
    int G = std::min(size[cir[i]][0], size[cir[i]][1]);
    S[i][0] = size[cir[i]][0] - G;
    S[i][1] = size[cir[i]][1] - G;
  }
  build(1, 1, L);
  for (int i = 1; i <= L; i++)
    for (int j = 0; j < 2; j++)
      while (S[i][j]) {
        std::pair<int, std::pair<int, int> > Nearest = Get(i, j);
        if (Nearest.first > N) {
          puts("-1");
          return;
        }
        int U = i == Nearest.second.first && j == Nearest.second.second
                    ? S[i][j] >> 1
                    : std::min(S[i][j],
                               S[Nearest.second.first][Nearest.second.second]);
        S[i][j] -= U;
        S[Nearest.second.first][Nearest.second.second] -= U;
        O += (long long)U * Nearest.first;
        update(i);
        update(Nearest.second.first);
      }
  printf("%lld\n", O);
}
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 1, u, v; i <= M; i++) {
    scanf("%d%d", &u, &v);
    add(u, v);
  }
  if (N & 1) {
    puts("-1");
    return 0;
  }
  if (M == N - 1)
    Tree();
  else
    Circle();
  return 0;
}
