#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:64000000")
using namespace std;
vector<vector<int> > f, b;
int u[1000000];
int d = 0;
int gcd(int a, int b) {
  while (b != 0) {
    int t = a % b;
    a = b;
    b = t;
  }
  return a;
}
void dfs(int x, int l) {
  u[x] = l;
  for (int i = 0; i < f[x].size(); i++) {
    int t = f[x][i];
    if (u[t] >= 0 && l + 1 != u[t])
      d = gcd(abs(l + 1 - u[t]), d);
    else if (u[t] == -1)
      dfs(t, l + 1);
  }
  for (int i = 0; i < b[x].size(); i++) {
    int t = b[x][i];
    if (u[t] >= 0 && l - 1 != u[t])
      d = gcd(abs(l - 1 - u[t]), d);
    else if (u[t] == -1)
      dfs(t, l - 1);
  }
  u[x] = -2;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  f.resize(n);
  b.resize(n);
  for (int i = 0; i < m; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    f[x - 1].push_back(y - 1);
    b[y - 1].push_back(x - 1);
  }
  fill(u, u + n, -1);
  for (int i = 0; i < n; i++)
    if (u[i] == -1) dfs(i, 1000000);
  printf("%d", d ? d : n);
  return 0;
}
