#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
inline void chmin(A &a, B b) {
  if (a > b) a = b;
}
template <typename A, typename B>
inline void chmax(A &a, B b) {
  if (a < b) a = b;
}
const long long INF = 1001001001001001001ll;
struct BinaryIndexedTree {
  long long n;
  vector<long long> dat;
  BinaryIndexedTree(long long n = 0) : n(n) { dat.resize(n + 1); }
  void add(long long k, long long x) {
    for (k++; k <= n; k += k & -k) dat[k] += x;
  }
  long long sum(long long k) {
    long long ret = 0;
    for (k++; k; k -= k & -k) ret += dat[k];
    return ret;
  }
};
long long N, M;
vector<long long> G[111111];
namespace S1 {
long long num[111111];
long long sz[111111];
long long ans = 0;
void dfs(long long v, long long p, long long c) {
  num[v] = c;
  sz[v] = 1;
  for (auto u : G[v]) {
    if (u == p) continue;
    dfs(u, v, 1 - c);
    num[v] += num[u];
    sz[v] += sz[u];
  }
  ans += abs(sz[v] - num[v] * 2);
}
void solve() {
  dfs(0, -1, 0);
  if (num[0] * 2 != N)
    cout << -1 << endl;
  else
    cout << ans << endl;
}
}  // namespace S1
vector<long long> T[111111];
vector<long long> C;
namespace S2 {
long long num[111111];
long long sz[111111];
long long ans = 0;
void dfs(long long v, long long p, long long c) {
  num[v] = c;
  sz[v] = 1;
  for (auto u : T[v]) {
    if (u == p) continue;
    dfs(u, v, 1 - c);
    num[v] += num[u];
    sz[v] += sz[u];
  }
  if (p != -1) ans += abs(sz[v] - num[v] * 2);
}
void solve() {
  long long n = C.size();
  vector<long long> A(n);
  for (long long i = 0; i < (C.size()); i++) {
    dfs(C[i], -1, i & 1);
    A[i] = sz[C[i]] - num[C[i]] * 2;
  }
  vector<long long> sum(2 * n + 1);
  for (long long i = 0; i < (2 * n); i++) {
    sum[i + 1] = sum[i] + A[i % n];
  }
  BinaryIndexedTree bit(1000000);
  BinaryIndexedTree bitnum(1000000);
  for (long long i = 0; i < (n - 1); i++) {
    bit.add(500000 + sum[i + 1], sum[i + 1]);
    bitnum.add(500000 + sum[i + 1], 1);
  }
  long long mi = INF;
  for (long long i = 0; i < n; i++) {
    bit.add(500000 + sum[i + n], sum[i + n]);
    bitnum.add(500000 + sum[i + n], 1);
    long long foo = bit.sum(1000000) - bit.sum(sum[i] + 500000);
    long long bar = n - bitnum.sum(sum[i] + 500000);
    long long tmp = 0;
    tmp += foo - bar * sum[i];
    foo = bit.sum(sum[i] + 500000);
    bar = bitnum.sum(sum[i] + 500000);
    tmp += bar * sum[i] - foo;
    chmin(mi, tmp);
    bit.add(500000 + sum[i + 1], -sum[i + 1]);
    bitnum.add(500000 + sum[i + 1], -1);
  }
  cout << ans + mi << endl;
}
}  // namespace S2
namespace S3 {
void solve() { assert(0); }
}  // namespace S3
signed main() {
  cin >> N >> M;
  for (long long i = 0; i < (M); i++) {
    long long a, b;
    cin >> a >> b;
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  if (M == N - 1) {
    S1::solve();
    return 0;
  }
  vector<long long> deg(N);
  for (long long i = 0; i < (N); i++)
    for (auto u : G[i]) deg[u]++;
  queue<long long> que;
  for (long long i = 0; i < (N); i++)
    if (deg[i] == 1) que.push(i);
  while (que.size()) {
    long long v = que.front();
    que.pop();
    for (auto u : G[v]) {
      deg[u]--;
      if (deg[u] >= 1) T[u].push_back(v);
      if (deg[u] == 1) que.push(u);
    }
  }
  long long v;
  for (long long i = 0; i < (N); i++)
    if (deg[i] == 2) v = i;
  while (true) {
    C.push_back(v);
    deg[v] = -1;
    long long k = -1;
    for (auto u : G[v])
      if (deg[u] == 2) k = u;
    if (k == -1) break;
    v = k;
  }
  if (C.size() % 2 == 0) {
    S2::solve();
  } else {
    S3::solve();
  }
  return 0;
}
