#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
const int N = 100001;
vector<int> A[N];
int F[N];
int n, m, k = 0;
int gcd(int a, int b) {
  if (a == 0 || b == 0) return a | b;
  return gcd(b, a % b);
}
void dfs(int x, int i) {
  F[x] = i;
  for (auto y : A[x]) {
    int sgn = y < 0 ? -1 : 1;
    if (y < 0) y = -y;
    if (!F[y])
      dfs(y, i + sgn);
    else {
      if (k == 0)
        k = abs(i + sgn - F[y]);
      else
        k = gcd(k, abs(i + sgn - F[y]));
    }
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < (m); i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    A[a].push_back(b);
    A[b].push_back(-a);
  }
  for (int i = (1); i <= (n); i++)
    if (!F[i]) dfs(i, n);
  if (k == 0) k = n;
  cout << k << endl;
  return 0;
}
