#include <bits/stdc++.h>
using namespace std;
const int N = 1000 * 100 + 5;
vector<int> en[N], ex[N];
queue<int> q;
int n, m, c = N, d;
int col[N];
bool mark[N];
void BFS(int v) {
  mark[v] = 1;
  q.push(v);
  while (!q.empty()) {
    int u = q.front();
    int siz = ex[u].size();
    for (int i = 0; i < siz; i++) {
      int t = ex[u][i];
      if (!mark[t]) {
        col[t] = col[u] + 1;
        q.push(t);
        mark[t] = 1;
      } else {
        if (col[u] + 1 != col[t]) {
          c = abs(col[u] + 1 - col[t]);
          while (!q.empty()) q.pop();
          return;
        }
      }
    }
    siz = en[u].size();
    for (int i = 0; i < siz; i++) {
      int t = en[u][i];
      if (!mark[t]) {
        col[t] = col[u] - 1;
        q.push(t);
        mark[t] = 1;
      } else {
        if (col[u] - 1 != col[t]) {
          c = abs(col[u] - 1 - col[t]);
          while (!q.empty()) q.pop();
          return;
        }
      }
    }
    q.pop();
  }
  return;
}
void BFS2(int v) {
  mark[v] = 1;
  col[v] = 0;
  q.push(v);
  while (!q.empty()) {
    int u = q.front();
    int siz = ex[u].size();
    for (int i = 0; i < siz; i++) {
      int t = ex[u][i];
      if (!mark[t]) {
        col[t] = (col[u] + 1) % d;
        q.push(t);
        mark[t] = 1;
      }
    }
    siz = en[u].size();
    for (int i = 0; i < siz; i++) {
      int t = en[u][i];
      if (!mark[t]) {
        col[t] = col[u] - 1;
        while (col[t] < 0) col[t] += d;
        q.push(t);
        mark[t] = 1;
      }
    }
    q.pop();
  }
  return;
}
bool solve() {
  for (int i = 0; i < n; i++) {
    if (!mark[i]) BFS2(i);
  }
  for (int i = 0; i < n; i++) {
    int siz = ex[i].size();
    for (int j = 0; j < siz; j++) {
      int u = ex[i][j];
      if ((col[i] + 1) % d != col[u]) return 0;
    }
  }
  return 1;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int x, y;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    cin >> x >> y;
    ex[--x].push_back(--y);
    en[y].push_back(x);
  }
  for (int i = 0; i < n; i++) {
    if (c > n && !mark[i]) BFS(i);
  }
  if (c > n) {
    cout << n;
    return 0;
  }
  for (int i = c; i >= 1; i--) {
    if (c % i == 0) {
      d = i;
      for (int j = 0; j < n; j++) mark[j] = 0;
      if (solve()) {
        cout << d;
        return 0;
      }
    }
  }
  return 0;
}
