#include <bits/stdc++.h>
using namespace std;
int n, m, cp = 0, ans = 0;
int hd[110000], ot[210000], nt[210000], v[210000];
bool u[110000];
int gcd(const int x, const int y) { return y == 0 ? x : gcd(y, x % y); }
void add(const int x, const int y, const int z) {
  ot[++cp] = y, nt[cp] = hd[x], hd[x] = cp, v[cp] = z;
}
int b[110000], d[110000];
void bfs(const int x) {
  int e, now, h = 1, t = 1;
  b[1] = x, d[x] = 0;
  u[x] = 1;
  for (; h <= t; ++h) {
    now = b[h];
    for (int i = hd[now]; i != 0; i = nt[i])
      if (!u[ot[i]]) {
        b[++t] = ot[i];
        u[ot[i]] = 1;
        d[ot[i]] = d[now] + v[i];
      } else if (d[ot[i]] != d[now] + v[i]) {
        e = abs(d[ot[i]] - d[now] - v[i]);
        ans = gcd(e, ans);
      }
  }
}
int main() {
  memset(u, 0, sizeof(u));
  memset(hd, 0, sizeof(hd));
  scanf("%d%d", &n, &m);
  for (int i = 1, o, p; i <= m; ++i) {
    scanf("%d%d", &o, &p);
    if (o == p) {
      puts("1");
      return 0;
    }
    add(o, p, 1);
    add(p, o, -1);
  }
  for (int i = 1; i <= n; ++i)
    if (u[i] == 0) bfs(i);
  if (ans == 0) ans = n;
  cout << ans << endl;
  return 0;
}
