#include <iostream>
#include <vector>

using namespace std;

bool vis[10000][10000];

int main() {
    int n,m;
    cin >> n >> m;
    vector <int> graph[n];
    int a,b;
    for (int i=0; i<m; i++) {
        cin >> a >> b;
        graph[a-1].push_back(b-n);
    }
    for (int i=0; i<n; i++) {
        for (int j=0; j<graph[i].size(); j++) {
            for (int k=0; k<graph[i].size(); k++) {
                int el1 = graph[i][j];
                int el2 = graph[i][k];
                if (el1==el2) {
                    continue;
                }
                //cout << el1 << " " << el2 << endl;
                if (vis[el1][el2]) {
                    cout << 2 << endl;
                    return 0;
                }
                vis[el1][el2] = true;
            }
        }
    }
    cout << 3 << endl;
}