#include <bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const long long maxn = 1e5 + 10;
vector<long long> v[maxn], g[maxn];
long long val[maxn];
bool mark[maxn];
long long ans;
long long gcd(long long a, long long b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
void modify(long long u, long long num) { ans = gcd(ans, abs(val[u] - num)); }
void dfs(long long u, long long num = 0) {
  if (mark[u] == 1) {
    modify(u, num);
    return;
  }
  mark[u] = 1;
  val[u] = num;
  for (long long i = 0; i < (v[u]).size(); i++) dfs(v[u][i], num + 1);
  for (long long i = 0; i < (g[u]).size(); i++) dfs(g[u][i], num - 1);
}
int main() {
  long long n, m;
  cin >> n >> m;
  set<pair<long long, long long> > s;
  long long cnt = 1;
  for (long long i = 1; i <= m; i++) {
    long long a, b;
    cin >> a >> b;
    if (!s.count(make_pair(a, b))) {
      s.insert(make_pair(a, b));
      v[a].push_back(b);
      g[b].push_back(a);
    }
  }
  for (long long i = 1; i <= n; i++) {
    if (!mark[i]) {
      dfs(i);
    }
  }
  if (ans == 0)
    cout << n;
  else
    cout << ans;
}
