#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000 * 100 + 100;
vector<int> dives, v[MAXN], vv[MAXN];
int h[MAXN], n, m, dor = -1, r[MAXN];
bool mark[MAXN];
bool dfs(int x, int c, int par) {
  if (h[x] && c != h[x]) {
    dor = abs(c - h[x]);
    return 1;
  }
  h[x] = c;
  for (auto u : v[x])
    if (u != par && c + 1 != h[u])
      if (dfs(u, c + 1, x)) return 1;
  for (auto u : vv[x])
    if (u != par && c - 1 != h[u])
      if (dfs(u, (c - 1), x)) return 1;
  return 0;
}
void dfs2(int x, int c, int &k) {
  mark[x] = 1;
  if (c == -1) c = k - 1;
  r[x] = c;
  for (auto u : v[x])
    if (!mark[u]) dfs2(u, (c + 1) % k, k);
  for (auto u : vv[x])
    if (!mark[u]) dfs2(u, (c - 1), k);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin >> n >> m;
  map<pair<int, int>, bool> ma;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    if (!ma[{a, b}]) {
      v[a].push_back(b);
      vv[b].push_back(a);
      ma[{a, b}] = 1;
    }
  }
  for (int i = 0; i < n; i++)
    if (!h[i] && dor == -1) dfs(i, n + 1, -1);
  if (dor == -1) {
    cout << n << endl;
    return 0;
  }
  for (int i = 1; i <= dor; i++)
    if (dor % i == 0) dives.push_back(dor / i);
  for (auto u : dives) {
    memset(mark, 0, sizeof(mark));
    for (int i = 0; i < n; i++)
      if (!mark[i]) dfs2(i, 0, u);
    bool flag = 1;
    for (int i = 0; i < n; i++)
      for (auto t : v[i])
        if (r[t] != (r[i] + 1) % u) flag = 0;
    if (flag) {
      cout << u << endl;
      return 0;
    }
  }
  return 0;
}
