#include <bits/stdc++.h>
using namespace std;
const int maxn = 110000;
vector<pair<int, int> > adj[maxn];
int cyc;
bool dag = 1;
int seen[maxn];
int k[maxn];
void dfs(int root, int K) {
  k[root] = K;
  for (auto e : adj[root]) {
    if (!seen[e.first]) {
      seen[e.first] = seen[root] + 1;
      dfs(e.first, K + e.second);
    } else {
      if (seen[root] <= seen[e.first]) {
        int w = k[e.first] - k[root] - e.second;
        if (w) cyc = abs(w);
      }
    }
  }
}
bool check(int K, int root, int t = 0) {
  k[root] = t;
  seen[root] = 1;
  bool ret = 1;
  for (auto x : adj[root]) {
    if (!seen[x.first]) {
      ret &= check(K, x.first, (t + x.second + K) % K);
    } else {
      ret &= ((t + x.second + K) % K == k[x.first]);
    }
  }
  return ret;
}
int32_t main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    adj[a].push_back(make_pair(b, +1));
    adj[b].push_back(make_pair(a, -1));
  }
  for (int i = 0; i < n; i++)
    if (!seen[i]) {
      seen[i] = 1;
      dfs(i, 0);
    }
  int ans = 1;
  if (!cyc) {
    cout << n << endl;
    exit(0);
  }
  for (int i = 1; i * i <= cyc; i++) {
    if (cyc % i == 0) {
      fill(seen, seen + n, 0);
      fill(k, k + n, 0);
      bool b = 1;
      for (int j = 0; j < n; j++)
        if (!seen[j]) {
          b &= check(i, j);
        }
      if (b) ans = max(ans, i);
      b = 1;
      fill(seen, seen + n, 0);
      fill(k, k + n, 0);
      for (int j = 0; j < n; j++)
        if (!seen[j]) {
          b &= check(cyc / i, j);
        }
      if (b) ans = max(ans, cyc / i);
    }
  }
  cout << ans << endl;
  return 0;
}
