#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i < (b); i++)
#define pb push_back
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
// #include <iostream>
// #include <vector>
// #include <queue>
// #include <string>
// #include <cmath>
// #include <cstdlib>
// #include <set>
// #include <iomanip>
// #include <limits>
// #include <map>
// #include <assert.h>
// #include <algorithm>
// #include <list>
// #include <iterator>
// #include <fstream>
// #include <random>
// #include <unordered_map>
// using namespace std;
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("bmi,bmi2,lzcnt,popcnt") // bit manipulation
// #pragma GCC target("movbe") // byte swap
// #pragma GCC target("aes,pclmul,rdrnd") // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2")
// typedef long long ll;
// #define rep(i, a, b) for (int i = (a); i < int(b); i++)
// typedef pair<ll, ll> pll;
// typedef pair<int, int> pii;
// #define pb push_back
// inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
// ll INF = 1000000000;
// ll mod = 1e9 + 7;
//
vector<pii> ans;
int moves = 0;
int done = 0;
int N, M;
int empty_spaces;
vector<bool> lonely_bottom;
vector<pii> bottoms;
vector<pii> tops;
priority_queue<array<int, 3>> pq;
void value(int b, int t)
{
//
assert (b != t);
assert (lonely_bottom[t] == false);
int ret = 0;
if (tops[t].second != -1) ret++;
if (lonely_bottom[b]) ret++;
if (tops[b].first != -1) ret++;
pq.push({ret, b, t});
// 0 , 1 , 2
// return ret;
}
void new_space(int b, int t)
{
if (b == -1) {
empty_spaces++;
return;
}
if (t == -1) {
if (lonely_bottom[b] == true) {
// lonely_bottom[b] = false;
// tops[b].first = -1; // b;
// bottoms[b].first = -1; // b;
moves++;
done++;
empty_spaces++;
return;
}
if (tops[b].first != -1) {
int tmp = tops[b].first;
tops[b].first = -1; // b
// bottoms[b].first = -1; // b;
int other;
if (bottoms[tmp].first != b) other = bottoms[tmp].first;
if (bottoms[tmp].second != b) other = bottoms[tmp].second;
bottoms[tmp] = {other, -1};
moves++;
done++;
new_space(tmp, -1);
return;
}
lonely_bottom[b] = true;
//
if (bottoms[b].first != -1) { // ?
value(b, bottoms[b].first);
}
if (bottoms[b].second != -1) {
value(b, bottoms[b].second);
}
return;
}
if (lonely_bottom[t] == true)
{
// lonely_bottom[t] = false;
// bottoms[t].first = -1; // t;
// tops[t].first = -1; // t;
moves++;
done++;
new_space(b, -1);
return;
}
if (b == t) {
done++;
return; //
}
if (tops[t].first != -1) tops[t].second = b;
else tops[t].first = b;
if (bottoms[b].first != -1) bottoms[b].second = t;
else bottoms[b].first = t;
}
int32_t main()
{
fast();
cin >> N >> M;
empty_spaces = 0;
lonely_bottom.assign(N, false);
bottoms.assign(N, {-1, -1});
tops.assign(N, {-1, -1});
int b, t;
rep(i,0,M)
{
cin >> b >> t;
b--; t--;
new_space(b, t);
}
// cerr << moves << " " << done << " " << empty_spaces << "\n";
//
int tmp;
rep(i,0,N)
{
if (tops[i].first != -1)
{
value(tops[i].first, i);
// pq.push({tmp, tops[i].first, i});
if (tops[i].second != -1)
{
value(tops[i].second, i);
// pq.push({tmp, tops[i].second, i});
}
}
}
// empty, done
while (!pq.empty() && empty_spaces > 0 && done != N)
{
array<int, 3> tmp1 = pq.top();
pq.pop();
int b = tmp1[1], t = tmp1[2];
if (!(tops[t].first == b || tops[t].second == b)) continue;
// val
int other;
if (tops[t].first != b) other = tops[t].first;
if (tops[t].second != b) other = tops[t].second; // -1
tops[t] = {other, -1};
if (bottoms[b].first != t) other = bottoms[b].first;
if (bottoms[b].second != t) other = bottoms[b].second; // -1
bottoms[b] = {other, -1};
moves++;
empty_spaces--;
new_space(b, -1);
new_space(t, -1); // ?
}
//
if (done == N)
{
cout << moves << "\n";
//
}
else cout << -1 << "\n";
}
