#include <bits/stdc++.h>
#pragma comment(linker, "/stack:64000000")
using namespace std;
template <typename first>
inline first abs(const first& a) {
  return a < 0 ? -a : a;
}
template <typename first>
inline first sqr(const first& a) {
  return a * a;
}
const long double PI = 3.1415926535897932384626433832795;
const long double EPS = 1e-9;
const int INF = 1000 * 1000 * 1000;
const int N = 100 * 1000 + 3;
int n, m;
vector<pair<int, int> > g[N];
int D = -1;
int num[N];
int used[N];
void dfs(int v, int curNum) {
  used[v] = true;
  num[v] = curNum;
  for (int i = 0; i < int(int((g[v]).size())); i++) {
    int to = g[v][i].first, w = g[v][i].second;
    if (num[to] != -1) {
      int delta = abs(num[to] - (curNum + w));
      if (delta != 0) D = delta;
    }
    if (!used[to]) dfs(to, curNum + w);
  }
}
int K;
bool go(int v, int curNum) {
  used[v] = true;
  num[v] = curNum;
  for (int i = 0; i < int(int((g[v]).size())); i++) {
    int to = g[v][i].first, w = g[v][i].second;
    if (num[to] != -1 && num[to] != (curNum + w + K) % K) return true;
    if (!used[to] && go(to, (curNum + w + K) % K)) return true;
  }
  return false;
}
bool check(int k) {
  memset(num, -1, sizeof(num));
  memset(used, 0, sizeof(used));
  K = k;
  for (int i = 0; i < int(n); i++)
    if (!used[i] && go(i, 0)) return false;
  return true;
}
int main() {
  memset(num, -1, sizeof(num));
  cin >> n >> m;
  for (int i = 0; i < int(m); i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    --a, --b;
    g[a].push_back(make_pair((b), (1)));
    g[b].push_back(make_pair((a), (-1)));
  }
  for (int i = 0; i < int(n); i++)
    if (!used[i]) dfs(i, 0);
  if (D == -1) {
    cout << n << endl;
    return 0;
  }
  for (int i = D; i >= 1; i--)
    if (D % i == 0 && check(i)) {
      cout << i << endl;
      return 0;
    }
  throw;
  return 0;
}
