#include <bits/stdc++.h>
using namespace std;
const int maxn = 100500;
const int inf = 1e9 + 100500;
int p[maxn];
int get(int x) { return x == p[x] ? x : (p[x] = get(p[x])); }
bool unite(int x, int y) {
  x = get(x), y = get(y);
  if (x == y) return false;
  p[x] = y;
  return true;
}
int n;
vector<int> e[maxn];
int d[maxn][2];
int d2[maxn][2];
pair<int, int> badEdge{-1, -1};
int initCol[maxn];
const int ROOT = 0;
void scan() {
  int m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < (int)(m); ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    --u, --v;
    if (unite(u, v)) {
      e[u].push_back(v);
      e[v].push_back(u);
    } else {
      assert(badEdge.first == -1);
      badEdge = {u, v};
    }
  }
}
void relax(int &x, int y) { x = min(x, y); }
void dfs(int v, int anc) {
  auto it = find((e[v]).begin(), (e[v]).end(), anc);
  if (it != e[v].end()) e[v].erase(it);
  int k = e[v].size();
  vector<array<int, 2>> d2(k + 1);
  for (int i = 0; i < (int)(k + 1); ++i) d2[i][0] = d2[i][1] = inf;
  d2[0][initCol[v]] = 0;
  for (int i = 0; i < (int)(k); ++i) {
    int to = e[v][i];
    dfs(to, v);
    for (int cur = 0; cur < (int)(2); ++cur)
      if (d2[i][cur] != inf) {
        relax(d2[i + 1][cur ^ 1], d2[i][cur] + d[to][0] + 1);
        relax(d2[i + 1][cur], d2[i][cur] + d[to][1]);
      }
  }
  d[v][0] = d2[k][0];
  d[v][1] = d2[k][1];
}
void solve() {
  int res = inf;
  dfs(ROOT, -1);
  res = min(res, d[ROOT][1]);
  if (badEdge.first != -1) {
    initCol[badEdge.first] = initCol[badEdge.second] = 1;
    dfs(ROOT, -1);
    res = min(res, d[ROOT][1]);
  }
  if (res == inf)
    cout << -1 << endl;
  else
    cout << res << endl;
}
int main() {
  iota(p, p + maxn, 0);
  scan();
  solve();
  return 0;
}
