#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const int MAXN = 100007;
int idx[MAXN];
vector<int> edge[MAXN], redge[MAXN];
int n, m;
int ans;
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
void go(int u) {
  for (typeof(edge[u].begin()) it = edge[u].begin(); it != edge[u].end();
       it++) {
    if (-11234567 == idx[*it]) {
      idx[*it] = idx[u] + 1;
      go(*it);
    } else {
      int delta = abs((idx[*it]) - (idx[u] + 1));
      if (delta) {
        if (ans == -1)
          ans = delta;
        else
          ans = gcd(ans, delta);
      }
    }
  }
  for (typeof(redge[u].begin()) it = redge[u].begin(); it != redge[u].end();
       it++) {
    if (-11234567 == idx[*it]) {
      idx[*it] = idx[u] - 1;
      go(*it);
    } else {
      int delta = abs((idx[*it] + 1) - (idx[u]));
      if (delta) {
        if (ans == -1)
          ans = delta;
        else
          ans = gcd(ans, delta);
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    edge[--u].push_back(--v);
    redge[v].push_back(u);
  }
  for (int i = 0; i < n; i++) idx[i] = -11234567;
  ans = -1;
  for (int i = 0; i < n; i++)
    if (-11234567 == idx[i]) {
      idx[i] = 0;
      go(i);
    }
  if (ans == -1) ans = n;
  cout << ans << endl;
  return 0;
}
