#include <bits/stdc++.h>
using namespace std;
int n, m, ans, u, v, tag[100009];
vector<int> g1[100009], g2[100009];
bool vis[100009];
int gcd(int a, int b) {
  while (b) b ^= a ^= b ^= a %= b;
  return a;
}
int abs(int a) { return a > 0 ? a : -a; }
void dfs(int rt) {
  vis[rt] = 1;
  for (int i = 0; i < g1[rt].size(); i++) {
    if (!vis[v = g1[rt][i]])
      tag[v] = tag[rt] + 1, dfs(v);
    else
      u = abs(tag[rt] + 1 - tag[v]), ans = ans ? gcd(ans, u) : u;
  }
  for (int i = 0; i < g2[rt].size(); i++) {
    if (!vis[v = g2[rt][i]])
      tag[v] = tag[rt] - 1, dfs(v);
    else
      u = abs(tag[rt] - 1 - tag[v]), ans = ans ? gcd(ans, u) : u;
  }
}
int main() {
  cin >> n >> m;
  while (m--) {
    cin >> u >> v;
    g1[u].push_back(v), g2[v].push_back(u);
  }
  for (int i = 1; i <= n; i++)
    if (!vis[i]) dfs(i);
  cout << (ans ? ans : n) << endl;
}
