#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:66777216")
using namespace std;
int a, b, c, d, i, j, n, m, k;
vector<pair<int, int> > sm[100001];
bool used[100001];
int num[100001];
vector<int> bad, cand;
void dfs(int v) {
  if (used[v]) return;
  used[v] = 1;
  for (int _n(((int)((sm[v]).size())) - 1), i(0); i <= _n; i++) {
    int w = sm[v][i].first, add = sm[v][i].second;
    if (used[w] && num[v] + add != num[w]) {
      bad.push_back(abs(num[v] + add - num[w]));
    } else if (!used[w]) {
      num[w] = num[v] + add;
      dfs(w);
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int _n((m)-1), i(0); i <= _n; i++) {
    scanf("%d%d", &a, &b);
    --a;
    --b;
    sm[a].push_back(make_pair(b, 1));
    sm[b].push_back(make_pair(a, -1));
  }
  for (int _n((n)-1), i(0); i <= _n; i++)
    if (!used[i]) dfs(i);
  sort((bad).begin(), (bad).end());
  bad.resize(unique((bad).begin(), (bad).end()) - bad.begin());
  for (int _n((n)), i(1); i <= _n; i++) cand.push_back(i);
  for (int _n(((int)((bad).size())) - 1), i(0); i <= _n; i++) {
    if (!bad[i]) {
      cerr << "HER" << endl;
      printf("%d\n", 1);
      exit(0);
    }
    a = 0;
    while (a < (int)((cand).size())) {
      if (bad[i] % cand[a]) {
        swap(cand[a], cand.back());
        cand.pop_back();
      } else
        ++a;
    }
  }
  printf("%d\n", *max_element((cand).begin(), (cand).end()));
}
