#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 2;
vector<pair<int, int> > p[N];
int n, m, num[N];
int res;
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
void dfs(int x, int v) {
  if (res && v < 1)
    v = res - (res - v) % res;
  else if (res && v > res)
    v = (v - 1) % res + 1;
  if (num[x] - v == 0) return;
  if (num[x] < n + 1) {
    res = gcd((num[x] - v) > 0 ? (num[x] - v) : -(num[x] - v), res);
    if (v > 0)
      v = (v - 1) % res + 1;
    else
      v = res - (res - v) % res;
  }
  num[x] = v;
  for (int i = 0; i < p[x].size(); ++i) dfs(p[x][i].first, v + p[x][i].second);
}
int main() {
  cin >> n >> m;
  while (m--) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    p[x].push_back(make_pair(y, 1));
    p[y].push_back(make_pair(x, -1));
  }
  for (int i = 0; i < n; ++i) num[i] = n + 1;
  for (int i = 0; i < n; ++i)
    if (num[i] > n) dfs(i, 1);
  if (!res) res = n;
  cout << res << endl;
  return 0;
}
