#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e5 + 13;
int n, m, ans, par[maxN], len, col[maxN];
bool mark[maxN], anc[maxN];
vector<int> adj[maxN], jda[maxN];
bool t;
vector<pair<int, int>> edge;
bool dfs2(int v, int c, int m) {
  col[v] = c;
  bool ret = 1;
  int nxtc = c + 1;
  if (nxtc == m + 1) nxtc = 1;
  int prec = c - 1;
  if (prec == 0) prec = m;
  for (auto a : adj[v]) {
    if (col[a] && col[a] != nxtc) return 0;
    if (!mark[a]) {
      mark[a] = 1;
      ret = ret & dfs2(a, nxtc, m);
    }
  }
  for (auto a : jda[v]) {
    if (col[a] && col[a] != prec) return 0;
    if (!mark[a]) {
      mark[a] = 1;
      ret = ret & dfs2(a, prec, m);
    }
  }
  return ret;
}
bool check(int x) {
  memset(col, 0, sizeof col);
  memset(mark, 0, sizeof mark);
  for (int i = 0; i < n; i++) {
    if (col[i] == 0)
      if (!dfs2(i, 1, x)) return 0;
  }
  return 1;
}
void dfs(int x, int c) {
  col[x] = c;
  mark[x] = 1;
  for (auto a : adj[x]) {
    if (!mark[a])
      dfs(a, c + 1);
    else
      len = max(len, abs(c + 1 - col[a]));
  }
  for (auto a : jda[x]) {
    if (!mark[a])
      dfs(a, c - 1);
    else {
      len = max(len, abs(c - 1 - col[a]));
    }
  }
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    adj[a].push_back(b);
    jda[b].push_back(a);
  }
  for (int i = 0; i < n; i++) {
    if (!mark[i]) {
      mark[i] = 1;
      dfs(i, 0);
    }
  }
  if (!len) return cout << n << endl, 0;
  for (int i = 1; i <= sqrt(len); i++)
    if (len % i == 0) {
      if (check(i)) ans = max(ans, i);
      if (check(len / i)) ans = max(ans, len / i);
    }
  cout << ans << endl;
}
