#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 * 1000 + 17;
int n, m, num[MAXN];
vector<pair<int, int> > adj[MAXN], ed;
bool mark[MAXN];
void dfs2(int v, int k) {
  mark[v] = true;
  for (auto i : adj[v]) {
    if (!mark[i.first]) {
      num[i.first] = (num[v] + i.second + k) % k;
      dfs2(i.first, k);
    }
  }
}
void fans(int x) {
  vector<int> div;
  for (int i = 1; i * i <= x; i++)
    if (x % i == 0) div.push_back(i), div.push_back(x / i);
  sort(div.begin(), div.end(), greater<int>());
  for (auto k : div) {
    for (int i = 1; i <= n; i++) mark[i] = false, num[i] = 0;
    for (int i = 1; i <= n; i++) dfs2(i, k);
    bool flag = true;
    for (auto e : ed)
      if ((num[e.first] + 1) % k != num[e.second] % k) flag = false;
    if (flag) {
      cout << k << endl;
      exit(0);
    }
  }
}
void dfs(int v) {
  mark[v] = 1;
  for (auto i : adj[v]) {
    if (!mark[i.first]) {
      num[i.first] = num[v] + i.second;
      dfs(i.first);
    } else {
      if (abs(num[i.first] - (num[v] + i.second)) != 0)
        fans(abs(num[i.first] - (num[v] + i.second)));
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int v, u;
    cin >> v >> u;
    adj[v].push_back({u, 1});
    adj[u].push_back({v, -1});
    ed.push_back({v, u});
  }
  for (int i = 1; i <= n; i++)
    if (!mark[i]) {
      num[i] = 1;
      dfs(i);
    }
  cout << n << endl;
  return 0;
}
