#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 100010;
int n, m, col[N], f[N], dep[N];
vector<int> e[N];

bool dfs1(int x, bool c){
    if(~col[x]) return col[x] ^ c;
    col[x] = c;
    for(int &y : e[x]) if(dfs1(y, c ^ 1)) return 1;
    return 0;
}

bool check_odd(){
    memset(col, -1, sizeof(col));
    rep(i, 1, n) if(!~col[i] && dfs1(i, 0)) return 1;
    return 0;
}

bool dfs2(int x, int fa){
    // printf("%d %d\n", x, fa);
    dep[x] = dep[fa] + 1;
    for(int &y : e[x]) if(y ^ fa){
        if(!dep[y]){
            if(dfs2(y, x)) return 1;
            f[x] += f[y];
        }
        else if(dep[y] < dep[x]){
            if((dep[x] ^ dep[y]) & 1) return 1;
            f[x]++, f[y]--;
            // printf("f[%d]++ f[%d]--\n", x, y);
        }
    }
    // printf("dfs2: %d %d\n", x, f[x]);
    return f[x] > 1;
}

bool check_even(){
    rep(i, 1, n) if(!dep[i] && dfs2(i, 0)) return 1;
    return 0;
}

bool check(){
    rep(i, 1, n) for(int &j : e[i]){
        if(e[i].size() == 1 || e[j].size() == 1) continue;
        if(e[i].size() > 2 || e[j].size() > 2) return 1;
        int x = (e[i][0] == j) ? e[i][1] : e[i][0];
        int y = (e[j][0] == i) ? e[j][1] : e[j][0];
        if(x != y) return 1;
    }
    return 0;
}

int main(){
    scanf("%d%d", &n, &m);
    rep(i, 1, m){
        int x, y; scanf("%d%d", &x, &y);
        e[x].push_back(y); e[y].push_back(x);
    }
    if(n <= 3) {puts("-1"); return 0;}
    if(m <= 2) {printf("%d\n", 5 - m); return 0;}
    bool flg1 = check_odd();
    bool flg2 = check_even();
    if(flg1 && flg2) {puts("0"); return 0;}
    if(flg2 && !flg1) {puts("1"); return 0;}
    int ans = !flg1 + 1 + !check();
    printf("%d\n", ans);
    return 0;
}