#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <int n, class... T>
typename enable_if<(n >= sizeof...(T))>::type _ot(ostream &,
                                                  tuple<T...> const &) {}
template <int n, class... T>
typename enable_if<(n < sizeof...(T))>::type _ot(ostream &os,
                                                 tuple<T...> const &t) {
  os << (n == 0 ? "" : ", ") << get<n>(t);
  _ot<n + 1>(os, t);
}
template <class... T>
ostream &operator<<(ostream &o, tuple<T...> const &t) {
  o << "(";
  _ot<0>(o, t);
  o << ")";
  return o;
}
template <class T, class U>
ostream &operator<<(ostream &o, pair<T, U> const &p) {
  o << "(" << p.first << ", " << p.second << ")";
  return o;
}
template <class T>
ostream &operator<<(ostream &o, const stack<T> &a) {
  o << "{";
  for (auto tmp = a; tmp.size(); tmp.pop())
    o << (a.size() == tmp.size() ? "" : ", ") << tmp.top();
  o << "}";
  return o;
}
template <class T,
          class = typename iterator_traits<typename T::iterator>::value_type,
          class = typename enable_if<!is_same<T, string>::value>::type>
ostream &operator<<(ostream &o, const T &a) {
  for (auto ite = a.begin(); ite != a.end(); ++ite)
    o << (ite == a.begin() ? "" : " ") << *ite;
  return o;
}
const int N = 1e5;
int n, m;
vector<vector<int>> g(N);
int cycleSize() {
  vector<int> used(n);
  vector<int> dist(n);
  const function<int(int, int)> dfs = [&](int i, int p) {
    if (used[i]) {
      return dist[p] + 1;
    }
    used[i] = 1;
    for (int j : g[i])
      if (j != p) {
        dist[j] = dist[i] + 1;
        int d = dfs(j, i);
        if (d != -1) return d;
      }
    return -1;
  };
  dist[0] = 0;
  return dfs(0, -1);
}
int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n >> m;
  if (n == 2) {
    cout << 1 << endl;
    return 0;
  }
  if (n % 2 == 1) {
    cout << -1 << endl;
    return 0;
  }
  vector<int> deg(n);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].emplace_back(b);
    g[b].emplace_back(a);
    deg[a]++;
    deg[b]++;
  }
  ll ans = 0;
  vector<vector<int>> w(2, vector<int>(n));
  vector<int> used(n);
  queue<int> q;
  for (int i = 0; i < n; i++) {
    w[0][i]++;
    if (g[i].size() == 1) {
      q.emplace(i);
    }
  }
  while (q.size()) {
    int i = q.front();
    q.pop();
    if (deg[i] == 0) {
      if (w[0][i] != w[1][i]) {
        cout << -1 << endl;
        return 0;
      }
      break;
    }
    used[i] = 1;
    int m = min(w[0][i], w[1][i]);
    w[0][i] -= m;
    w[1][i] -= m;
    ans += w[0][i] | w[1][i];
    for (int j : g[i])
      if (!used[j]) {
        deg[j]--;
        for (int c = 0; c < 2; c++) w[1 - c][j] += w[c][i];
        if (deg[j] == 1) {
          q.emplace(j);
        }
        break;
      }
  }
  (42);
  if (n == m) {
    int circ = cycleSize();
    (42);
    int start;
    for (int i = 0; i < n; i++)
      if (deg[i] == 2) start = i;
    int last;
    for (int j : g[start])
      if (deg[j] == 2) last = j;
    int now = start;
    vector<int> v;
    vector<int> cnt(2);
    while (1) {
      int x = v.size();
      v.emplace_back(now);
      for (int c = 0; c < 2; c++) cnt[(x & 1) ^ c] += w[c][now];
      for (int j : g[now])
        if (deg[j] == 2 && j != last) {
          last = now;
          now = j;
          break;
        }
      if (now == start) break;
    }
    if (circ % 2 == 0) {
      int res = 1e9;
      for (int t = 0; t < 2; t++) {
        auto f = [&](int mid) {
          int res = 0;
          auto wc = w;
          wc[t][v[0]] += mid;
          for (int i = 0; i < (int)v.size() - 1; i++) {
            int m = min(wc[0][v[i]], wc[1][v[i]]);
            wc[0][v[i]] -= m;
            wc[1][v[i]] -= m;
            res += wc[0][v[i]] | wc[1][v[i]];
            for (int c = 0; c < 2; c++) wc[1 - c][v[i + 1]] += wc[c][v[i]];
          }
          return res + mid;
        };
        int ok = n, ng = -1;
        for (int i = ng + 1; i <= n; i++) {
          (42);
        }
        while (ok - ng > 1) {
          int mid = (ok + ng) >> 1;
          if (f(mid) <= f(mid + 1))
            ok = mid;
          else
            ng = mid;
        }
        (42);
        res = min(res, f(ok));
      }
      ans += res;
    } else {
      (42);
      cnt[0] -= cnt[1];
      if (cnt[0] % 2 != 0) return cout << -1 << endl, 0;
      cnt[0] /= 2;
      if (cnt[0] > 0) {
        ans += cnt[0];
        w[1][v[0]] += cnt[0];
        w[1][v.back()] += cnt[0];
      } else {
        ans += -cnt[0];
        w[0][v[0]] += -cnt[0];
        w[0][v.back()] += -cnt[0];
      }
      for (int i = 0; i < (int)v.size() - 1; i++) {
        int m = min(w[0][v[i]], w[1][v[i]]);
        w[0][v[i]] -= m;
        w[1][v[i]] -= m;
        (42);
        ans += w[0][v[i]] | w[1][v[i]];
        for (int c = 0; c < 2; c++) w[1 - c][v[i + 1]] += w[c][v[i]];
      }
      assert(w[0][v.back()] == w[1][v.back()]);
      assert(0);
    }
  }
  cout << ans << endl;
  return 0;
}
