#include <bits/stdc++.h>
using namespace std;
const int iinf = 1000000000;
const long long linf = 1000000000000000000;
const double dinf = 1e200;
struct vec {
  double x, y;
  vec() {}
  vec(double x, double y) : x(x), y(y) {}
  double dot(const vec &b) const { return x * b.x + y * b.y; }
  double len() const { return sqrt(dot(*this)); }
  vec pp() const { return vec(y, -x); }
  vec &operator+=(const vec &b) {
    x += b.x;
    y += b.y;
    return *this;
  }
  vec &operator-=(const vec &b) {
    x -= b.x;
    y -= b.y;
    return *this;
  }
  vec &operator*=(double b) {
    x *= b;
    y *= b;
    return *this;
  }
  vec &operator/=(double b) {
    x /= b;
    y /= b;
    return *this;
  }
  vec operator+(const vec &b) const { return vec(x + b.x, y + b.y); }
  vec operator-(const vec &b) const { return vec(x - b.x, y - b.y); }
  vec operator*(double b) const { return vec(x * b, y * b); }
  vec operator/(double b) const { return vec(x / b, y / b); }
  vec normd() const { return (*this) * (1. / len()); }
};
int gcd(int a, int b) { return a ? gcd(b % a, a) : b; }
vector<pair<int, int> > ugr[110000];
int bal[110000];
int col[110000];
bool was[110000];
int D;
int n;
void dfs1(int v, int b) {
  if (was[v]) {
    D = gcd(D, abs(b - bal[v]));
    return;
  }
  was[v] = true;
  bal[v] = b;
  for (int i = 0; i < (int)((ugr[v]).size()); ++i) {
    int p = ugr[v][i].first;
    dfs1(p, b + ugr[v][i].second);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  int m;
  cin >> n >> m;
  for (int i = 0; i < (int)(m); ++i) {
    int a, b;
    cin >> a >> b;
    --a;
    --b;
    ugr[a].push_back(make_pair(b, 1));
    ugr[b].push_back(make_pair(a, -1));
  }
  for (int i = 0; i < (int)(n); ++i)
    if (!was[i]) dfs1(i, 0);
  if (!D) D = n;
  cout << D;
  return 0;
}
