#include <bits/stdc++.h>
using namespace std;
const int maxn = 100 * 1000 + 1000;
vector<pair<int, int> > v[maxn];
int dis[maxn], col[maxn];
bool mark[maxn];
vector<int> a;
int n, m;
int dfs(int x) {
  mark[x] = true;
  int ret = -1;
  for (int i = 0; i < v[x].size(); i++) {
    int child = v[x][i].first, e = v[x][i].second;
    if (mark[child] == false) {
      dis[child] = dis[x] + e;
      ret = max(ret, dfs(child));
    } else if (dis[x] - dis[child] + e != 0)
      ret = max(ret, dis[x] - dis[child] + e);
  }
  return ret;
}
bool chk(int k) {
  memset(col, -1, sizeof col);
  queue<int> q;
  for (int i = 0; i < n; i++)
    if (col[i] == -1) {
      col[i] = 0;
      q.push(i);
      while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < v[x].size(); i++)
          if (col[v[x][i].first] == -1) {
            col[v[x][i].first] = (col[x] + v[x][i].second + k) % k;
            q.push(v[x][i].first);
          } else if (col[v[x][i].first] != (col[x] + v[x][i].second + k) % k)
            return false;
      }
    }
  return true;
}
int main() {
  cin >> n >> m;
  while (m--) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    v[x].push_back(make_pair(y, 1));
    v[y].push_back(make_pair(x, -1));
  }
  int cc = -1;
  for (int i = 0; i < n; i++)
    if (mark[i] == false) cc = max(cc, dfs(i));
  if (cc == -1) {
    cout << n << endl;
    return 0;
  }
  for (int i = 1; i * i <= cc; i++)
    if (cc % i == 0) a.push_back(i), a.push_back(cc / i);
  sort(a.begin(), a.end());
  for (int i = a.size() - 1; i >= 0; i--)
    if (chk(a[i])) {
      cout << a[i] << endl;
      return 0;
    }
  return 0;
}
