#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, ed, ret;
int l[100005], v[100005], qd[100005 + 100005], qn[100005 + 100005],
    qw[100005 + 100005];
int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
void dfs(int x, int y) {
  if (v[x]) {
    int d = abs(v[x] - y);
    if (!d) return;
    if (ret > n)
      ret = d;
    else
      ret = gcd(ret, d);
    return;
  } else
    v[x] = y;
  for (int i = (l[x]); i; i = qn[i]) dfs(qd[i], y + qw[i]);
}
void bd(int x, int y, int w) {
  qd[++ed] = y, qw[ed] = w, qn[ed] = l[x], l[x] = ed;
}
int main() {
  scanf("%d%d", &n, &m);
  while (m--) {
    scanf("%d%d", &x, &y);
    bd(x, y, 1);
    bd(y, x, -1);
  }
  ret = n + 1;
  for (int i = (1); i <= (n); i++)
    if (!v[i]) dfs(i, n + 1);
  if (ret > n) ret = n;
  printf("%d\n", ret);
  return 0;
}
