#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
int n;
int m;
vector<pair<int, int> > g[100000];
bool w[100000];
int col[100000];
int ans = 0;
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
void dfs(int u, int c) {
  w[u] = false;
  col[u] = c;
  for (int i = 0; i < (((int)(g[u]).size())); i++) {
    int v = g[u][i].first;
    int cc = c + g[u][i].second;
    if (w[v]) {
      dfs(v, cc);
    } else {
      ans = gcd(ans, abs(cc - col[v]));
    }
  }
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < (m); i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--;
    v--;
    g[u].push_back(make_pair(v, 1));
    g[v].push_back(make_pair(u, -1));
  }
  memset(w, true, sizeof(w));
  for (int i = 0; i < (n); i++) {
    if (w[i]) {
      dfs(i, 0);
    }
  }
  cout << (ans ? ans : n) << endl;
  return 0;
}
