#include <bits/stdc++.h>
using namespace std;
template <class T>
void read(T &res) {
  res = 0;
  T f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    res = res * 10 + c - '0';
    c = getchar();
  }
  res *= f;
}
template <class T>
void out(T x) {
  if (x < 0) {
    x = -x;
    putchar('-');
  }
  if (x >= 10) {
    out(x / 10);
  }
  putchar('0' + x % 10);
}
struct node {
  int to, next;
} E[100005 * 2];
int N, head[100005], sumE, M, fa[100005], dep[100005], st, ed;
long long dp[100005][2], ans, pre[100005], suf[100005], prez[100005][2],
    sufz[100005][2];
bool vis[100005];
int c[100005], tot;
int sta[100005], top, num[100005];
void add(int u, int v) {
  E[++sumE].to = v;
  E[sumE].next = head[u];
  head[u] = sumE;
}
void dfs(int u) {
  dp[u][0] = 1;
  for (int i = head[u]; i; i = E[i].next) {
    int v = E[i].to;
    if (v != fa[u]) {
      fa[v] = u;
      dfs(v);
      ans += dp[v][0] + dp[v][1];
      dp[u][0] += dp[v][1];
      dp[u][1] += dp[v][0];
    }
  }
  int t = min(dp[u][0], dp[u][1]);
  dp[u][0] -= t;
  dp[u][1] -= t;
}
void find_circle(int u) {
  dep[u] = dep[fa[u]] + 1;
  vis[u] = 1;
  for (int i = head[u]; i; i = E[i].next) {
    int v = E[i].to;
    if (!vis[v]) {
      fa[v] = u;
      find_circle(v);
    } else if (dep[v] < dep[u]) {
      st = u;
      ed = v;
    }
  }
}
void Calc(int u) {
  dp[u][0] = 1;
  vis[u] = 1;
  for (int i = head[u]; i; i = E[i].next) {
    int v = E[i].to;
    if (!vis[v]) {
      Calc(v);
      ans += dp[v][0] + dp[v][1];
      dp[u][0] += dp[v][1];
      dp[u][1] += dp[v][0];
    }
  }
  int t = min(dp[u][0], dp[u][1]);
  dp[u][0] -= t;
  dp[u][1] -= t;
}
void Solve() {
  read(N);
  read(M);
  int a, b;
  for (int i = 1; i <= M; ++i) {
    read(a);
    read(b);
    add(a, b);
    add(b, a);
  }
  if (N & 1) {
    puts("-1");
    return;
  }
  if (M == N - 1) {
    dfs(1);
    if (dp[1][0] || dp[1][1]) {
      puts("-1");
      return;
    }
    out(ans);
    putchar('\n');
  } else {
    find_circle(1);
    int p = st;
    while (1) {
      c[++tot] = p;
      if (p == ed) break;
      p = fa[p];
    }
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i <= tot; ++i) vis[c[i]] = 1;
    for (int i = 1; i <= tot; ++i) {
      Calc(c[i]);
    }
    top = 0;
    for (int i = 1; i <= tot; ++i) {
      int u = c[i];
      pre[i] = pre[i - 1];
      if (dp[u][0] || dp[u][1]) {
        pre[i] += (i - 1) * (dp[u][0] + dp[u][1]);
      }
      for (int k = 0; k <= 1; ++k) {
        int t = k ^ ((i - 1) & 1);
        int cnt = dp[u][k];
        while (cnt && top && num[top] == t ^ 1) {
          pre[i] -= sta[top] * 2;
          --top;
          --cnt;
        }
        if (cnt) {
          for (int j = 1; j <= cnt; ++j) {
            sta[++top] = i - 1;
            num[top] = t;
          }
        }
      }
      if (top) prez[i][num[top]] = top;
    }
    top = 0;
    for (int i = tot; i >= 1; --i) {
      int u = c[i];
      suf[i] = suf[i + 1];
      if (dp[u][0] || dp[u][1]) {
        suf[i] += (tot - i) * (dp[u][0] + dp[u][1]);
      }
      for (int k = 0; k <= 1; ++k) {
        int t = k ^ ((tot - i) & 1);
        int cnt = dp[u][k];
        while (cnt && top && num[top] == t ^ 1) {
          suf[i] -= sta[top] * 2;
          --top;
          --cnt;
        }
        if (cnt) {
          for (int j = 1; j <= cnt; ++j) {
            sta[++top] = tot - i;
            num[top] = t;
          }
        }
      }
      if (top) sufz[i][num[top]] = top;
    }
    long long res = 1e18;
    if (prez[tot][0] + prez[tot][1] == 0) res = pre[tot];
    for (int i = 1; i < tot; ++i) {
      if (prez[i][0] == sufz[i + 1][0] && prez[i][1] == sufz[i + 1][1]) {
        res = min(res, pre[i] + suf[i + 1] + prez[i][0] + prez[i][1]);
      }
    }
    if (res >= 1e18) {
      puts("-1");
      return;
    }
    out(ans + res);
    putchar('\n');
  }
}
int main() {
  Solve();
  return 0;
}
