#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<queue<pair<int, int>>> tap(2);
    vector<int> noe(circ * 4);
    vector<int> ids(circ * 4);
    vector<int> type(circ * 4);
    int x = -1;
    while (1) {
      x++;
      int m = min(w[0][now], w[1][now]);
      w[0][now] -= m;
      w[1][now] -= m;
      int t = !w[0][now];
      for (int i = 0; i < 4; i++) {
        type[x + circ * i] = t ^ (x & 1) ^ ((circ * i) & 1);
        noe[x + circ * i] = w[t][now];
      }
      for (int j : g[now])
        if (deg[j] == 2 && j != last) {
          last = now;
          now = j;
          break;
        }
      if (now == start) break;
    }
    assert(x == circ - 1);
    for (int i = 0; i < circ * 4 - 1; i++) {
      ids[i + 1] = ids[i] + noe[i];
    }
    int num = ids.back() + noe.back();
    (42);
    vector<int> next(num, -1);
    vector<int> prev(num, -1);
    vector<int> idToX(num);
    vector<int> idToType(num);
    int cnt = 0;
    for (int i = 0; i < circ * 4; i++) {
      for (int j = 0; j < noe[i]; j++) {
        tap[type[i]].emplace(i, ids[i] + j);
        idToX[ids[i] + j] = i;
        idToType[ids[i] + j] = type[i];
        if (type[i]) cnt++;
      }
    }
    if (num != cnt * 2) {
      cout << -1 << endl;
      return 0;
    }
    for (int i = 0; i < circ * 4; i++) {
      auto &eca = tap[1 - type[i]];
      while (eca.size() && eca.front().first < i) eca.pop();
      for (int j = 0; j < noe[i]; j++) {
        int id0 = ids[i] + j;
        if (eca.size() && prev[id0] == -1) {
          int id1 = eca.front().second;
          next[id0] = id1;
          prev[id1] = id0;
          eca.pop();
        }
      }
    }
    for (int i = 0; i < 2; i++)
      while (tap[i].size()) tap[i].pop();
    for (int i = 0; i < circ * 4; i++) {
      for (int j = 0; j < noe[i]; j++) {
        if (prev[ids[i] + j] == -1) tap[type[i]].emplace(i, ids[i] + j);
      }
    }
    for (int i = 0; i < circ * 4; i++) {
      auto &eca = tap[1 - type[i]];
      while (eca.size() && eca.front().first < i) eca.pop();
      for (int j = 0; j < noe[i]; j++) {
        int id0 = ids[i] + j;
        if (eca.size() && next[id0] == -1) {
          int id1 = eca.front().second;
          next[id0] = id1;
          prev[id1] = id0;
          eca.pop();
        }
      }
    }
    vector<vector<int>> xv;
    vector<vector<vector<int>>> sum(2);
    vector<int> lid;
    vector<int> leader(num);
    {
      int k = -1;
      for (int i = 0; i < num; i++) {
        if (prev[i] == -1) {
          k++;
          lid.emplace_back(i);
          xv.push_back({});
          sum[0].push_back({});
          sum[1].push_back({});
          for (int now = i; now != -1; now = next[now]) {
            leader[now] = k;
            xv.back().emplace_back(idToX[now]);
            sum[0].back().emplace_back(0);
            sum[1].back().emplace_back(0);
          }
        }
      }
      assert(k + 1 == lid.size());
    }
    (42);
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < sum[i].size(); j++) {
        for (int l = 0; l < sum[i][j].size(); l++) {
          if (l + 1 < sum[i][j].size()) {
            sum[i][j][l] = type[xv[j][l]] == i ? xv[j][l + 1] - xv[j][l] : 0;
          }
          if (l) sum[i][j][l] += sum[i][j][l - 1];
        }
      }
    }
    vector<int> qina(lid.size());
    vector<int> isInvalid(lid.size());
    int invalid = 0;
    auto get = [&](int i, int l) {
      l = lower_bound((xv[i]).begin(), (xv[i]).end(), l) - begin(xv[i]);
      int r = lower_bound((xv[i]).begin(), (xv[i]).end(), l + circ * 2) -
              begin(xv[i]);
      if (l == xv[i].size()) return 0;
      if (r < 1) return 0;
      isInvalid[i] = type[xv[i][l]] ^ type[xv[i][r - 1]] ^ 1;
      if (l == r) return 0;
      int t = type[xv[i][l]];
      int res = 0;
      if (r - 2 >= 0) res = sum[t][i][r - 2];
      if (l - 1 >= 0) res -= sum[t][i][l - 1];
      return res;
    };
    ll res = 0;
    for (int i = 0; i < lid.size(); i++) {
      int id = lid[i];
      qina[i] = get(i, 0);
      res += qina[i];
      invalid += isInvalid[i];
    }
    assert(invalid == 0);
    ll eca = res;
    for (int i = 0; i < circ * 2; i++) {
      for (int j = 0; j < noe[i]; j++) {
        int id = ids[i] + j;
        res -= qina[leader[id]];
        invalid += isInvalid[leader[i]];
        qina[leader[id]] = get(leader[id], i + 1);
        res += qina[leader[id]];
        invalid += isInvalid[leader[i]];
      }
      for (int j = 0; j < noe[i + circ * 2]; j++) {
        int id = ids[i + circ * 2] + j;
        res -= qina[leader[id]];
        invalid -= isInvalid[leader[i]];
        qina[leader[id]] = get(leader[id], i + 1);
        res += qina[leader[id]];
        invalid += isInvalid[leader[i]];
      }
      if (invalid == 0) eca = min(eca, res);
    }
    ans += eca / 2;
  }
  cout << ans << endl;
  return 0;
}
