// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
// }}}
// #include<bits/stdc++.h>
using namespace std;
using ll = long long;

// #undef DEBUG
// #define DEBUG
// DEBUG {{{
#include <stack>
#include <tuple>
#include <valarray>
#include <vector>
// clang-format off
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; }
#ifdef DEBUG
#if !defined(DEBUG_OUT)
#define DEBUG_OUT cerr
#endif
#if !defined(DEBUG_LEFT)
#define DEBUG_LEFT "\e[1;36m"
#endif
#if !defined(DEBUG_RIGHT)
#define DEBUG_RIGHT ":\e[m"
#endif
#define dump(...) [&](){auto __debug_tap=make_tuple(__VA_ARGS__);DEBUG_OUT<<DEBUG_LEFT<<__LINE__ << DEBUG_RIGHT << " " <<#__VA_ARGS__<<" = "<<__debug_tap<<endl;}()
template < class T > inline void dump2D(T &d, size_t sizey, size_t sizex) { for(size_t i = 0; i < sizey; i++) { DEBUG_OUT << "\t"; for(size_t j = 0; j < sizex; j++) DEBUG_OUT << d[i][j] << (j + 1 == sizex ? "" : "\t"); DEBUG_OUT << endl; } }
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) { o << "{"; for(auto ite = a.begin(); ite != a.end(); ++ite) o << (ite == a.begin() ? "" : ", ") << *ite; o << "}"; return o; }
#else
#define dump(...) (42)
#define dump2D(...) (42)
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; }
#endif
// clang-format on
// }}}


const int N = 1e5;
int n, m;
vector<vector<int>> g(N);

#include<functional>

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) { // is leaf
      q.emplace(i);
    }
  }
  while(q.size()) {
    int i = q.front(); q.pop();
    if(deg[i] == 0) {
      // n == m - 1
      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;
    }
  }
  dump(ans);
  if(n == m) {
    int start;
    for(int i = 0; i < n; i++) if(deg[i] == 2) start = i;
    dump(start);
    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];

      // next
      for(int j : g[now]) if(deg[j] == 2 && j != last) {
        last = now;
        now = j;
        break;
      }
      if(now == start) break;
    }
    
    int circ = v.size();
    dump(circ);

    if(circ % 2 == 0) {
      if(cnt[0] != cnt[1]) return cout << -1 << endl, 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;
        while(ok - ng > 1) {
          int mid = (ok + ng) >> 1;
          if(f(mid) <= f(mid + 1)) ok = mid;
          else ng = mid;
        }
        // dump(ok, f(ok));
        res = min(res, f(ok));
      }
      ans += res;
    } else {
      dump(cnt[0], cnt[1]);
      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;
        // dump(w[0][v[i]], w[1][v[i]]);
        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;
}


Measured memory_bytes: 8948