#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
void qread(int &x) {
  int neg = 1;
  x = 0;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') neg = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = 10 * x + c - '0', c = getchar();
  x *= neg;
}
const int maxn = 100005;
int n, m;
vector<int> edge[maxn];
int dp[maxn][2][2], tmp[2][2];
void dfs(int x, int p) {
  dp[x][0][0] = 0;
  if (p) dp[x][1][1] = 1;
  for (int(i) = 0; (i) < edge[x].size(); i++) {
    int y = edge[x][i];
    if (y == p) continue;
    dfs(y, x);
    for (int(c) = 0; (c) < 2; c++)
      for (int(t) = 0; (t) < 2; t++) tmp[c][t] = 0x3f3f3f3f;
    for (int(c) = 0; (c) < 2; c++)
      for (int(t) = 0; (t) < 2; t++)
        for (int(cc) = 0; (cc) < 2; cc++)
          for (int(tt) = 0; (tt) < 2; tt++) {
            if (cc == 1)
              tmp[c ^ tt][t] = min(tmp[c ^ tt][t], dp[x][c][t] + dp[y][cc][tt]);
            if ((c ^ tt) == cc && (!cc))
              tmp[c ^ tt ^ 1][t] =
                  min(tmp[c ^ tt ^ 1][t], dp[x][c][t] + dp[y][cc][tt] + 1);
            else if ((c ^ tt) != cc && p && (!c))
              tmp[c ^ tt][t ^ 1] =
                  min(tmp[c ^ tt][t ^ 1], dp[x][c][t] + dp[y][cc][tt] + 2);
          }
    for (int(c) = 0; (c) < 2; c++)
      for (int(t) = 0; (t) < 2; t++) dp[x][c][t] = tmp[c][t];
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int(i) = 1; (i) <= m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    edge[u].push_back(v);
    edge[v].push_back(u);
  }
  memset(dp, 0x3f, sizeof(dp));
  dfs(1, 0);
  printf("%d\n", dp[1][1][0] == 0x3f3f3f3f ? -1 : dp[1][1][0]);
  return 0;
}
