#include<bits/stdc++.h>
using namespace std;
#define time chrono::system_clock::now().time_since_epoch().count()
mt19937_64 rnd(time);
#define maxn 1000005
// #define int long long

int read() {int x;cin>>x;return x;}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int n = read(), m = read();
    vector f(n + 1, vector(n + 1, (bool)0));
    vector<vector<int>>g(n + n + 1);
    for(int i = 1; i <= m; i++) {
        int aa = read(), bb = read();
        g[bb].push_back(aa);
    }
    for(int i = n + 1; i <= 2 * n; i++) {
        for(int j = 0; j < g[i].size(); j++) {
            int u = g[i][j];
            for(int k = j + 1; k < g[i].size(); k++) {
                int v = g[i][k];
                f[u][v] = 1;
                f[v][u] = 1;
                if(f[u][v]) {
                    cout << "2\n";
                    return 0;
                }
            }
        }
    }
    cout << "3\n";
    return 0;
}