#include <bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
using ll=long long;
vector<pair<int,int>> ve[20010];
bool flag[200010];
int dep[20010];
void dfs(int u,int v){
    dep[u]=dep[v]+1;
    for(auto i:ve[u]){
        if(dep[i.first])  continue;
        flag[i.second]=1;
        dfs(i.first,u);
    }
}
void solve() {
    int n,m;
    cin>>n>>m;
    int u,v;
    for(int i=1;i<=m;i++){
        cin>>u>>v;
        ve[u].push_back({v,i});
        ve[v].push_back({u,i});
    }
    dfs(1,1);
    vector<int> vk;
    for(int i=1;i<=2*n;i++){
        vk.clear();
        for(auto j:ve[i]){
            if(!flag[j.second]){
                vk.push_back(j.first);
                if(abs(dep[j.first]-dep[i])+1==4){
                    cout<<2<<'\n';
                    return ;
                }
            }
        }
        sort(vk.begin(),vk.end(),[&](int a,int b){return dep[a]<dep[b];});
        int sz=vk.size();
        for(int i=0;i<sz-1;i++){
            if(dep[vk[i+1]]-dep[vk[i]]+2==4){
                cout<<2<<'\n';
                return ;
            }
        }
        //if(i==5)    for(auto j:vk)  cout<<j<<' ';
        cout<<'\n';
    }  
    cout<<3<<'\n';
    return ;
}
int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int _ = 1;
    //cin >> _;
    while(_--) solve();
    return 0;
}