#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define ft first
#define sc second
#define pb push_back
#define all(x) x.begin(), x.end()
#define pi pair<int, int>
#define vi vector<int>
#define tii tuple<int, int, int>
#define tiii tuple<int, int, int, int>
#define tiiii tuple<int, int, int, int, int>
#define vpi vector<pi>
#define vtii vector<tii>
#define vtiii vector<tiii>
const int N = (1 << 20), MOD = 1e9 + 7, INF = int(1e18);
int arr[N], poz[N], k[N], wsk[N], cnt, e;
bool vis[N], gd[N], st[N];
int md(int x, int p){
if(x <= p) return x;
return x - p;
}
int oth(int x, int p){
if(x <= p) return x + p;
return x - p;
}
bool empt(int x){return (arr[x] == 0);}
queue<int> cur;
int psh(){
while(!cur.empty() && !empt(cur.front())) cur.pop();
if(cur.empty()) return -1;
return cur.front();
}
vpi ans;
vi z[N];
void mv(int x, int p, int n, int m){
int a = poz[x];
p = md(p, m);
ans.pb({md(a, m), p});
if(a > m) cur.push(a);
arr[a] = 0;
if(!empt(p + m)){
gd[md(x, n)] = 1;
cnt--;
}else p += m;
poz[x] = p;
arr[p] = x;
}
void check_clr(int x, int n, int m){
int c = md(x, n);
if(gd[c]) return;
int y = oth(x, n);
int a = poz[x], b = poz[y];
if(a > m && !empt(a - m)) return;
if(b > m && !empt(b - m)) return;
if(max(a, b) <= m) return;
if(a > m){
swap(a, b);
swap(x, y);
}
mv(x, b, n, m);
if(a <= m) check_clr(arr[a + m], n, m);
}
int dfs(int x, int n, int m){
if(vis[x]){
if(k[x] == 0) k[x] = x;
return k[x];
}
int u = poz[x];
vis[x] = 1;
if(u <= m){
wsk[x] = arr[u + m];
st[wsk[x]] = 1;
return k[x] = dfs(wsk[x], n, m);
}
int y = oth(x, n);
wsk[x] = y;
st[y] = 1;
if(poz[y] > m) return k[x] = y;
return k[x] = dfs(y, n, m);
}
void check_cmp(int x, int n, int m){
x = md(x, n);
if(z[x].empty() || gd[x]) return;
int a = z[x][0], b;
if(z[x].size() < 2) b = a;
else b = z[x][1];
if(!gd[md(a, n)] && poz[a] <= m){
e = psh();
int p = poz[a];
mv(a, e, n, m);
check_clr(a, n, m);
check_clr(arr[p + m], n, m);
if(!st[oth(a, n)]) check_cmp(k[oth(a, n)], n, m);
}
if(!gd[md(b, n)] && poz[b] <= m){
e = psh();
int p = poz[b];
mv(b, e, n, m);
check_clr(b, n, m);
check_clr(arr[p + m], n, m);
if(!st[oth(b, n)]) check_cmp(k[oth(b, n)], n, m);
}
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL); cout.tie(NULL);
// random_device rd;
// mt19937_64 gen(rd());
int n, m;
cin >> n >> m;
cnt = n;
for(int i = 1; i <= m; i++){
cin >> arr[i + m] >> arr[i];
if(vis[arr[i]]) arr[i] += n;
if(arr[i] != 0) vis[arr[i]] = 1;
if(vis[arr[i + m]]) arr[i + m] += n;
vis[arr[i + m]] = 1;
poz[arr[i]] = i;
poz[arr[i + m]] = i + m;
vis[0] = 0;
}
gd[0] = 1;
for(int i = 1; i <= n; i++){
vis[i] = vis[i + n] = 0;
if(md(poz[i], m) == md(poz[i + n], m)){
gd[i] = 1;
cnt--;
}
check_clr(i, n, m);
}
for(int i = 1; i <= m; i++) cur.push(i + m);
if(cnt > 0 && psh() < 0){
cout << "-1\n";
return 0;
}
for(int i = 1; i <= 2 * n; i++){
if(poz[i] <= m && !gd[i]) dfs(i, n, m);
}
for(int i = 1; i <= 2 * n; i++){
if((st[i] && k[i] != i) || gd[md(i, n)]) continue;
if(k[i] == i){
e = psh();
int a = poz[i];
mv(i, e, n, m);
check_clr(i, n, m);
check_clr(arr[a + m], n, m);
}else z[md(k[i], n)].pb(i);
}
for(int i = 1; i <= n; i++){
if(z[i].size() < 2 || md(z[i][0], n) == md(z[i][1], n)) check_cmp(i, n, m);
}
e = psh();
while(!cur.empty() && cur.front() == e) cur.pop();
if(cnt > 0 && psh() < 0){
cout << "-1\n";
return 0;
}
cur.push(e);
for(int i = 1; i <= n; i++) check_cmp(i, n, m);
cout << int(ans.size()) << "\n";
// for(auto [i, j] : ans) cout << i << ' ' << j << "\n";
return 0;
}
