#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
vector<int> Matrix[MAXN], Matrixre[MAXN];
int n, m, t1, t2, ans, Color[MAXN];
bool Used[MAXN];
unsigned GCD(unsigned u, unsigned v) {
  while (v != 0) {
    unsigned r = u % v;
    u = v;
    v = r;
  }
  return u;
}
void DFS(int v, int cl) {
  Color[v] = cl;
  Used[v] = true;
  for (int i = 0; i < Matrix[v].size(); i++)
    if (!Used[Matrix[v][i]]) DFS(Matrix[v][i], cl + 1);
  for (int i = 0; i < Matrixre[v].size(); i++)
    if (!Used[Matrixre[v][i]]) DFS(Matrixre[v][i], cl - 1);
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> t1 >> t2;
    Matrix[t1].push_back(t2);
    Matrixre[t2].push_back(t1);
  }
  for (int i = 1; i <= n; i++) {
    if (!Used[i]) DFS(i, 0);
  }
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < Matrix[i].size(); j++)
      ans = GCD(ans, abs(Color[i] - Color[Matrix[i][j]] + 1));
  if (ans == 0) ans = n;
  cout << ans;
}
