#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
constexpr int INF = (1 << 30);
constexpr ll INFL = (1ll << 60);
constexpr ll MOD = 1000000007;
int N, M;
vector<set<int>> to;
void input() {
  cin >> N >> M;
  to.resize(N);
  int a, b;
  for (ll((i)) = (0); ((i)) < ((M)); ((i))++) {
    cin >> a >> b;
    a--;
    b--;
    to[a].insert(b);
    to[b].insert(a);
  }
}
using pis = pair<int, set<int>*>;
auto c = [](pis o1, pis o2) { return o1.second->size() > o2.second->size(); };
using PQ = priority_queue<pis, vector<pis>, decltype(c)>;
PQ linkerOrder() {
  PQ pq(c);
  for (ll((i)) = (0); ((i)) < ((N)); ((i))++) pq.push({i, &to[i]});
  return pq;
}
bool paint(pis now, vector<bool>& black) {
  if (black[now.first]) return false;
  black[now.first] = true;
  for (auto& node : *now.second) {
    black[node] = !black[node];
  }
  return true;
}
void trim(pis now) {
  int here = now.first;
  for (auto& obj : *now.second) {
    to[obj].erase(here);
  }
}
void calc() {
  vector<bool> black(N, false);
  auto pq = linkerOrder();
  int res = 0;
  while (pq.size() > 1) {
    auto node = pq.top();
    pq.pop();
    if (node.second->size() != 1) cerr << "error" << endl;
    if (paint(node, black)) res++;
    trim(node);
  }
  bool success = true;
  for (auto obj : black) success &= obj;
  cout << (success ? res : -1) << endl;
}
void output() {}
void debug() {
  int N;
  cin >> N;
}
int main() {
  input();
  calc();
  output();
  debug();
  return 0;
}
