#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
constexpr int M=4e5+5;ull pos[M];
int n,m,tp,u[M],v[M],to[M],cnt[M],deg[M],stk[M];
int read(){
    int x=0;char ch=getchar();
    while (!isdigit(ch)) ch=getchar();
    while (isdigit(ch)) x=x*10+ch-48,ch=getchar();
    return x;
}
int main(){
    n=read()<<1;m=read();
    for (int i=1;i<=m;i++)
        deg[u[i]=read()]++,
        deg[v[i]=read()]++;
    for (int i=1;i<=n;i++) pos[i]=((ull)deg[i])<<32|i;
    for (int i=1;i<=n;i++) deg[i+1]+=deg[i];
    for (int i=1;i<=m;i++)
        to[--deg[u[i]]]=v[i],
        to[--deg[v[i]]]=u[i];
    for (int i=1;i<=m;i++){
        for (int x=deg[i];x<deg[i+1];x++){
            const int j=to[x];
            if (pos[i]<=pos[j]) continue;
            for (int y=deg[j];y<deg[j+1];y++){
                const int k=to[y];
                if (pos[i]<=pos[k]) continue;
                if (cnt[k]++) return puts("2");
                stk[++tp]=k;
            }
        }
        while (tp) cnt[stk[tp--]]=0;
    }
    puts("3");
    return 0;
}