#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf INT_MAX
#define fr(i,l,r) for (i=(l); i<=(r); i++)
#define rfr(i,l,r) for (i=(l); i>=(r); i--)
template<typename T>inline void read(T &n){
    T w=1; n=0; char ch=getchar();
    while (!isdigit(ch) && ch!=EOF){ if (ch=='-') w=-1; ch=getchar(); }
    while (isdigit(ch) && ch!=EOF){ n=(n<<3)+(n<<1)+(ch&15); ch=getchar(); }
    n*=w;
}
template<typename T>inline void write(T x){
    if (x==0){ putchar('0'); return ; }
    T tmp;
    if (x>0) tmp=x;
    else tmp=-x;
    if (x<0) putchar('-');
    char F[105];
    long long cnt=0;
    while (tmp){
        F[++cnt]=tmp%10+48;
        tmp/=10;
    }
    while (cnt) putchar(F[cnt--]);
}
#define Min(x,y) x = min(x,y)
#define Max(x,y) x = max(x,y)
//基础配置=================================================================================
const ll N = 100005 , M = 200005;
ll n,m,ans=0,x,y,l,r,s,z;
struct edge{
    ll x,y;
};
ll cnt=0,head[N]; edge e[2*N];
void addedge(ll x,ll y){
    cnt++;
    e[cnt].x = head[x];
    e[cnt].y = y;
    head[x] = cnt;
}
ll opt[N];
bool flag;
void dfs(ll x,ll v){
    if (flag) return ;
    if (opt[x]==v) return ;
    if (opt[x]!=-1){
        flag = true;
        return ;    
    }
    opt[x] = v;
    for (ll i=head[x]; i; i=e[i].x){
        ll go = e[i].y;
        dfs(go,v^1);
    }
}
bool check1(){//判奇环
    memset(opt,-1,sizeof(opt));
    flag = false;
    for (ll i=1; i<=n; i++)
        if (opt[i]==-1) dfs(i,0);
    return flag;
}
ll fa[N];
bool vis[N];
void change(ll x,ll rt){
    if (flag) return ;
    while (x!=rt){
        if (opt[x]==1){
            flag = true;
            return ;
        }
        opt[x] = 1;
        x = fa[x];
    }
}
void dfs2(ll x,ll ft){
    fa[x] = ft;
    if (vis[x]) return ;
    vis[x] = true;
    for (ll i=head[x]; i; i=e[i].x){
        ll go = e[i].y;
        if (!vis[go]) dfs2(go,x);
        else change(x,go);
    }
}
bool check2(){//判偶环
    //生成dfs树
    //如果有相交的环，一定有解
    //否则直接判环长
    memset(vis,false,sizeof(vis));
    memset(opt,0,sizeof(opt));
    flag = false;
    for (ll i=1; i<=n; i++)
        if (!vis[i]) dfs2(i,-1);
    return flag;
}
ll d[N];
ll sum1,sum2;
void dfs3(ll x){
    if (vis[x]) return ;
    sum1++;
    if (d[x]>1) sum2++;
    vis[x] = true;
    for (ll i=head[x]; i; i=e[i].x) dfs3(e[i].y);
}
ll max_dis(){
    ll i,j;
    fr(i,1,n)
        for (j=head[i]; j; j=e[j].x) d[i]++;
    // fr(i,1,n) printf("d[%lld] = %lld\n",i,d[i]);
    memset(vis,false,sizeof(vis));
    fr(i,1,n){
        if (!vis[i]){
            sum1 = sum2 = 0;
            dfs3(i);
            if (sum1>3 && sum2>1) return 3;
        }
    }
    fr(i,1,n)
        if (d[i]>1) return 2;
    return 1;
}
int main(){
	// freopen("a.in","r",stdin);
//	freopen(".out","w",stdout);
    ll i,j;
    read(n); read(m);
    if (n<=3){
        printf("-1\n");
        return 0;
    }
    if (m<=2){
        printf("%lld\n",5-m);
        return 0;
    }
    fr(i,1,m){
        read(x); read(y);
        addedge(x,y);
        addedge(y,x);
    }
    //判奇偶环
    bool t1,t2;
    t1 = check1(); t2 = check2();
    // t1 = check1(); printf("t1 : %lld\n",(ll)t1);
    // t2 = check2(); printf("t2 : %lld\n",(ll)t2);
    if (t1 && t2){
        printf("0\n");
        return 0;
    }
    if (t2 && !t1){
        printf("1\n");
        return 0;
    }
    ll dis = max_dis();
    // printf("dis = %lld\n",dis);
    if (dis==3){
        ll ans = 0;
        if (!t1) ans++;
        if (!t2) ans++;
        write(ans);
        return 0;
    }
    if (dis==2){
        ll ans = 1;
        if (!t1) ans++;
        if (!t2) ans++;
        write(ans);
        return 0;
    }
    if (dis==1){
        ll ans = 2;
        if (!t1) ans++;
        if (!t2) ans++;
        write(ans);
        return 0;
    }
    return 0;
}
//g++ a.cpp -o a -Wall -Wl,--stack=512000000