#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, m, l[maxn], deg[maxn], onc[maxn], _vis[maxn], s[maxn], _a[maxn], a[maxn],
    cnt, e;
int sum[maxn * 2], val[maxn];
long long sumi[maxn * 2];
long long cost = 0;
struct Edge {
  int v, x;
} E[maxn << 1];
inline void addEdge(int u, int v) { E[e].v = v, E[e].x = l[u], l[u] = e++; }
int dfs(int u, int f, int t = 1) {
  int ret = t;
  for (int p = l[u]; p >= 0; p = E[p].x) {
    int v = E[p].v;
    if (v != f && !onc[v]) {
      ret += dfs(v, u, -t);
    }
  }
  if (f) cost += (ret < 0) ? (-ret) : ret;
  return ret;
}
void findcycle(int u) {
  a[++cnt] = s[u];
  _vis[u] = 1;
  for (int p = l[u]; p >= 0; p = E[p].x) {
    int v = E[p].v;
    if (onc[v] && !_vis[v]) {
      findcycle(v);
      return;
    }
  }
}
int lowbit(int x) { return x & (-x); }
void add(int p, int v) {
  for (int i = p; i <= 2 * n; i += lowbit(i)) {
    sum[i] += v;
    sumi[i] += (p - n) * v;
  }
}
int ask(int p) {
  int ret = 0;
  for (int i = p; i; i -= lowbit(i)) {
    ret += sum[i];
  }
  return ret;
}
long long aski(int p) {
  long long ret = 0;
  for (int i = p; i; i -= lowbit(i)) {
    ret += sumi[i];
  }
  return ret;
}
long long solve1(int x) {
  long long ret = 0;
  int t = x;
  for (int i = 1; i <= cnt; i++) {
    if (a[i] > 0) {
      int c = min(a[i], t);
      t -= c;
      a[i] -= c;
      ret += 1ll * (i - 1) * c;
    }
  }
  t = x;
  for (int i = cnt; i >= 1; i--) {
    if (a[i] > 0) {
      int c = min(a[i], t);
      t -= c;
      a[i] -= c;
      ret += 1ll * (cnt - i) * c;
    }
  }
  ret += x;
  return ret;
}
long long solve2() {
  int c = 0;
  long long ret = 1e18, cur = 0;
  int p1 = 1, p2 = cnt;
  for (int i = 1; i <= cnt; i++) val[i] = val[i - 1] + a[i];
  for (int i = 1; i < cnt; i++) add(n + val[i], 1);
  while (p1 < p2) {
    long long res = 0;
    res += (aski(2 * n) - aski(n + c)) - 1ll * c * (ask(2 * n) - ask(n + c));
    res += 1ll * c * ask(n + c) - aski(n + c);
    ret = min(ret, res + cur);
    while (p1 < p2 && a[p1] <= 0) {
      add(n + val[p1], -1);
      long long x = val[p1] - c;
      if (x < 0)
        cur -= x;
      else
        cur += x;
      ++p1;
    }
    while (p1 < p2 && a[p2] >= 0) {
      --p2;
      add(n + val[p2], -1);
      long long x = val[p2] - c;
      if (x < 0)
        cur -= x;
      else
        cur += x;
    }
    if (p1 < p2) {
      ++c;
      cur += p1 - 1 + cnt - p2 + 1;
      --a[p1], ++a[p2];
    }
  }
  return ret;
}
int main() {
  memset(l, -1, sizeof(l));
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    addEdge(u, v);
    addEdge(v, u);
    ++deg[u], ++deg[v];
  }
  if (m == n - 1) {
    int res = dfs(1, 0);
    if (res)
      puts("-1");
    else
      printf("%lld\n", cost);
    return 0;
  }
  queue<int> q;
  for (int i = 1; i <= n; i++)
    if (deg[i] == 1) q.push(i);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int p = l[u]; p >= 0; p = E[p].x) {
      int v = E[p].v;
      --deg[v];
      if (deg[v] == 1) {
        q.push(v);
      }
    }
  }
  for (int i = 1; i <= n; i++)
    if (deg[i] > 1) onc[i] = 1;
  for (int i = 1; i <= n; i++) {
    if (onc[i]) {
      s[i] = dfs(i, 0);
    }
  }
  for (int i = 1; i <= n; i++) {
    if (onc[i]) {
      findcycle(i);
      break;
    }
  }
  for (int i = 1; i <= cnt; i += 2) a[i] = -a[i];
  int t = 0;
  for (int i = 1; i <= cnt; i++) t += a[i];
  if (cnt & 1) {
    if (t < 0) {
      for (int i = 1; i <= cnt; i++) a[i] = -a[i];
      t = -t;
    }
    cost += solve1(t / 2);
    for (int i = 1; i <= cnt; i++) val[i] = val[i - 1] + a[i];
    for (int i = 1; i < cnt; i++) {
      if (val[i] < 0)
        cost -= val[i];
      else
        cost += val[i];
    }
  } else {
    if (t) {
      puts("-1");
      return 0;
    }
    long long res = 1e18;
    for (int i = 1; i <= cnt; i++) _a[i] = a[i];
    res = min(res, solve2());
    for (int i = 1; i <= cnt; i++) a[i] = -_a[i];
    res = min(res, solve2());
    cost += res;
  }
  printf("%lld\n", cost);
  return 0;
}
