#include <iostream>
#include <assert.h>
#include <cstring>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;

#define fo(x) freopen(#x ".in", "r", stdin), freopen(#x ".out", "w", stdout)
#define f1(i,k) for(int i=1,end_i=(k);i<=end_i;i++)
#define f0(i,k) for(int i=0,end_i=(k);i< end_i;i++)
#define cle(x) memset(x, 0, sizeof(x))
#define lobit(x) ((x) & -(x))
#define ll long long
#define pb push_back

inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}

#define int long long

const int inf = 2e18;
const int lim = 10010;
const int mv  = 1500;

int n,m;
int u,v;
vector<int> g[lim];
int a[lim], deg[lim], rk[lim], c[lim];

signed main(){
    cin>>n>>m;
    
    f1(i,m){
        cin>>u>>v;
        g[u].pb(v);
        g[v].pb(u);
        deg[u]++;
        deg[v]++;
        
    }
    
    f1(i,n) a[i] = i;
    
    sort(a+1, a+n+1, [&](int x, int y){return deg[x] < deg[y] || (deg[x] == deg[y] && x < y);});
    f1(i,n){
        rk[a[i]]=i;
    }
    
    int s = 0;
    
    f1(i,n)
        {
            for(int j:g[i])if(rk[i]>rk[j])for(int k:g[j])if(rk[i]>rk[k])s+=c[k]++;
            for(int j:g[i])if(rk[i]>rk[j])for(int k:g[j])c[k]=0;
            if(s)break;
        }
    if(s)cout<<2;
    else cout<<3;
    
    return 0;
}