#include <bits/stdc++.h>
using namespace std;
std::string dbgDelim(int &i) { return (i++ == 0 ? "" : ", "); }
template <class T>
std::ostream &operator<<(std::ostream &os, std::vector<T> v);
template <class T>
std::ostream &operator<<(std::ostream &os, std::set<T> v);
template <class T>
std::ostream &operator<<(std::ostream &os, std::queue<T> q);
template <class T>
std::ostream &operator<<(std::ostream &os, std::priority_queue<T> q);
template <class T, class K>
std::ostream &operator<<(std::ostream &os, std::pair<T, K> p);
template <class T, class K>
std::ostream &operator<<(std::ostream &os, std::map<T, K> mp);
template <class T, class K>
std::ostream &operator<<(std::ostream &os, std::unordered_map<T, K> mp);
template <int INDEX, class TUPLE>
void dbgDeploy(std::ostream &os, TUPLE tuple) {}
template <int INDEX, class TUPLE, class H, class... Ts>
void dbgDeploy(std::ostream &os, TUPLE t) {
  os << (INDEX == 0 ? "" : ", ") << get<INDEX>(t);
  dbgDeploy<INDEX + 1, TUPLE, Ts...>(os, t);
}
template <class T, class K>
void dbgDeploy(std::ostream &os, std::pair<T, K> p, std::string delim) {
  os << "(" << p.first << delim << p.second << ")";
}
template <class... Ts>
std::ostream &operator<<(std::ostream &os, std::tuple<Ts...> t) {
  os << "(";
  dbgDeploy<0, std::tuple<Ts...>, Ts...>(os, t);
  os << ")";
  return os;
}
template <class T, class K>
std::ostream &operator<<(std::ostream &os, std::pair<T, K> p) {
  dbgDeploy(os, p, ", ");
  return os;
}
template <class T>
std::ostream &operator<<(std::ostream &os, std::vector<T> v) {
  {
    int i = 0;
    os << "{";
    {
      for (T t : v) {
        os << dbgDelim(i) << t;
      };
    }
    os << "}";
    return os;
  };
}
template <class T>
std::ostream &operator<<(std::ostream &os, std::set<T> s) {
  {
    int i = 0;
    os << "{";
    {
      for (T t : s) {
        os << dbgDelim(i) << t;
      };
    }
    os << "}";
    return os;
  };
}
template <class T>
std::ostream &operator<<(std::ostream &os, std::queue<T> q) {
  {
    int i = 0;
    os << "{";
    {
      for (; q.size(); q.pop()) {
        os << dbgDelim(i) << q.front();
      };
    }
    os << "}";
    return os;
  };
}
template <class T>
std::ostream &operator<<(std::ostream &os, std::priority_queue<T> q) {
  {
    int i = 0;
    os << "{";
    {
      for (; q.size(); q.pop()) {
        os << dbgDelim(i) << q.top();
      };
    }
    os << "}";
    return os;
  };
}
template <class T, class K>
std::ostream &operator<<(std::ostream &os, std::map<T, K> mp) {
  {
    int i = 0;
    os << "{";
    {
      for (auto p : mp) {
        os << dbgDelim(i);
        dbgDeploy(os, p, "->");
      };
    }
    os << "}";
    return os;
  };
}
template <class T, class K>
std::ostream &operator<<(std::ostream &os, std::unordered_map<T, K> mp) {
  {
    int i = 0;
    os << "{";
    {
      for (auto p : mp) {
        os << dbgDelim(i);
        dbgDeploy(os, p, "->");
      };
    }
    os << "}";
    return os;
  };
}
const int64_t MAX = 100500;
vector<int64_t> edges[MAX];
class Res {
 public:
  int64_t myColor;
  int64_t score;
  Res(int64_t myColor, int64_t score) : myColor(myColor), score(score) {}
};
Res recur(int64_t pos, int64_t parent, vector<int64_t> &initial_colors) {
  Res res(initial_colors[pos], 0);
  for (int64_t child : edges[pos])
    if (child != parent) {
      Res r = recur(child, pos, initial_colors);
      res.score += r.score;
      if (r.myColor == 0) {
        res.score += 1;
        res.myColor = 1 - res.myColor;
      }
    }
  return res;
}
pair<int64_t, int64_t> findLoop(int64_t pos, int64_t parent,
                                vector<int64_t> &used) {
  if (used[pos]) return make_pair(pos, parent);
  used[pos] = true;
  for (int64_t child : edges[pos])
    if (child != parent) {
      pair<int64_t, int64_t> p = findLoop(child, pos, used);
      if (p.first != -1) return p;
    }
  return make_pair(-1, -1);
}
int main() {
  int64_t n, m;
  cin >> n >> m;
  for (int64_t i = 0; i < ((int64_t)(m)); ++i) {
    int64_t a, b;
    cin >> a >> b;
    edges[a - 1].push_back(b - 1);
    edges[b - 1].push_back(a - 1);
  }
  if (m == n - 1) {
    vector<int64_t> initial_colors(n, 0);
    Res res = recur(0, -1, initial_colors);
    cout << (res.myColor == 0 ? -1 : res.score) << endl;
    return 0;
  }
  vector<int64_t> find_loop_used(n, false);
  pair<int64_t, int64_t> p = findLoop(0, -1, find_loop_used);
  for (int64_t step = 0; step < ((int64_t)(2)); ++step) {
    p = make_pair(p.second, p.first);
    for (int64_t i = 0; i < ((int64_t)(((int64_t)((edges[p.first]).size()))));
         ++i)
      if (edges[p.first][i] == p.second) {
        swap(edges[p.first][i], edges[p.first].back());
        edges[p.first].pop_back();
        break;
      }
  }
  vector<int64_t> initial_colors0(n, 0);
  vector<int64_t> initial_colors1(n, 0);
  initial_colors1[p.first] = 1;
  initial_colors1[p.second] = 1;
  Res res0 = recur(0, -1, initial_colors0);
  Res res1 = recur(0, -1, initial_colors1);
  vector<int64_t> ans;
  if (res0.myColor == 1) ans.push_back(res0.score);
  if (res1.myColor == 1) ans.push_back(res1.score + 1);
  sort((ans).begin(), (ans).end());
  cout << (ans.empty() ? -1 : ans[0]) << endl;
}
