#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int col[100005] = {0}, ans;
bool vis[100005] = {false};
vector<pair<int, int> > adj[100005], ps;
void DFS(int v, int c) {
  vis[v] = true;
  col[v] = c;
  int h = adj[v].size();
  for (int i = 0; i < h; i++)
    if (!vis[adj[v][i].first])
      DFS(adj[v][i].first, c + adj[v][i].second);
    else
      ans = gcd(ans, (((c + adj[v][i].second - col[adj[v][i].first]) > (0))
                          ? (c + adj[v][i].second - col[adj[v][i].first])
                          : (-(c + adj[v][i].second - col[adj[v][i].first]))));
  return;
}
int main() {
  int n, m, v, u, k;
  scanf("%d%d", &n, &m);
  while (m--) {
    scanf("%d%d", &v, &u);
    adj[v].push_back(make_pair(u, 1));
    adj[u].push_back(make_pair(v, -1));
  }
  for (int i = 1; i <= n; i++)
    if (!vis[i]) DFS(i, 0);
  if (!ans) ans = n;
  cout << ans << endl;
  return 0;
}
