#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
typedef pair<int,int>PII;
const int N=1e5+5;
const int M=4e5+5;
int n,m;
int h[N],num,ne[M],to[M];
int st[N],co[N];
int fa[N][20],depth[N];
int sum[N];
PII e[N];int len;
int ans0,ans1;
map<PII,int>mp;
void add(int a,int b){
    ne[num]=h[a],to[num]=b,h[a]=num++;
}
void dfs(int u,int father){
    st[u]=1,fa[u][0]=father;
    for(int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    depth[u]=depth[father]+1;
    for(int i=h[u];~i;i=ne[i]){
        int j=to[i];
        if(st[j]) continue;
        mp[make_pair(j,u)]=mp[make_pair(u,j)]=1;
        dfs(j,u);
    }
    return;
}
int lca(int a,int b){
    if(depth[a]<depth[b]) swap(a,b);
    for(int i=1;i<20;i++) if(depth[fa[a][i]]>=depth[b]) a=fa[a][i];
    if(a==b) return a;
    for(int i=1;i<20;i++) if(fa[a][i]!=fa[b][i]) a=fa[a][i],b=fa[b][i];
    return fa[a][0];
}
void dfs1(int u,int father){
    for(int i=h[u];~i;i=ne[i]){
        int j=to[i];
        if(fa[j][0]!=u) continue;
        dfs1(j,u);
        sum[u]+=sum[j];
    }
    return;
}
void dfs2(int u,int cl){
    co[u]=cl;st[u]=1;
    for(int i=h[u];~i;i=ne[i]){
        int j=to[i];
        if(!st[j]) dfs2(j,cl^1);
        else if(co[j]!=(cl^1)) ans1=1;
    }
    return;
}
int main(){
    scanf("%d%d",&n,&m);
    memset(h,-1,sizeof(h));
    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
        e[++len]=make_pair(u,v);
    }
    for(int i=1;i<=n;i++) if(!st[i]) dfs(i,0);
    for(int i=1;i<=len;i++){
        int u=e[i].first,v=e[i].second;
        if(mp.count(make_pair(u,v))) continue;
        int l=lca(u,v);
        int dis=depth[u]+depth[v]-depth[l]-depth[fa[l][0]]+1;
        if(dis%2==0) ans0=1;
        else ans1=1;
        sum[u]++,sum[v]++,sum[l]-=2;;
    }
    for(int i=1;i<=n;i++) if(fa[i][0]==0) dfs1(i,0);
    for(int i=1;i<=n;i++) if(sum[i]>=2) ans0=1;
    memset(st,0,sizeof(st));
    for(int i=1;i<=n;i++) if(!st[i]) dfs2(i,0);
    if(n<=3){puts("-1");return 0;}
    if(m<=2){printf("%d\n",5-m);return 0;}
    if(ans0 && ans1){puts("0");return 0;}
    int ans3=0;
    for(int u=1;u<=n;u++)
        for(int i=h[u];~i;i=ne[i]){
            int v=to[i];
            for(int ii=h[v];~ii;ii=ne[ii]){
                int w=to[ii];
                if(u!=w) {ans3=1;goto next;}
            }
        }
    next:;
    if(ans1){
        if(ans3) puts("1");
        else puts("2");
    }
    else if(ans0) puts("1");
    else{
        if(ans3) puts("2");
        else puts("3");
    }
    return 0;
}