#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <random>
#include <ctime>
#include <cstdlib>
#include <chrono>

using namespace std;

int ap[10001][10001];

void solve() {
  int n, m;
  cin >> n >> m;

  vector<vector<int>> v(2 * n + 1);

  for (int i = 1; i <= m; ++i) {
    int x, y;
    cin >> x >> y;

    v[x].push_back(y + n);
    v[y + n].push_back(x + n);
  }

  for (int x = 1; x <= n; ++x) {
    for (int i = 0; i < v[x].size(); ++i) {
      int n1 = v[x][i];
      for (int j = i + 1; j < v[x].size(); ++j) {
        int n2 = v[x][j];
        if (ap[n1][n2]) {
          cout << 2 << '\n';
          return;
        }
        ap[n1][n2] = 1;
      }
    }
  }

  cout << 3 << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);

  int t = 1;
  // cin >> t;
  while (t--)
    solve();

  return 0;
}