#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
struct edge {
  int v;
  bool b;
};
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
void update(int &ans, int dif) {
  if (ans == -1)
    ans = dif;
  else
    ans = gcd(ans, dif);
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  static vector<edge> G[100000];
  for (int i = 0; i < (m); i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--;
    v--;
    G[u].push_back((edge){v, true});
    G[v].push_back((edge){u, false});
  }
  int ans = -1;
  static int color[100000];
  for (int u = 0; u < (n); u++) color[u] = INF;
  for (int u0 = 0; u0 < (n); u0++)
    if (color[u0] == INF) {
      color[u0] = 0;
      queue<int> Q;
      Q.push(u0);
      while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        for (int i = 0; i < (G[u].size()); i++) {
          int v = G[u][i].v, b = G[u][i].b;
          if (color[v] == INF) {
            color[v] = color[u] + (b ? 1 : -1);
            Q.push(v);
          } else {
            if (b) {
              if (color[u] + 1 != color[v])
                update(ans, abs(color[u] + 1 - color[v]));
            } else {
              if (color[u] - 1 != color[v])
                update(ans, abs(color[u] - 1 - color[v]));
            }
          }
        }
      }
    }
  if (ans == -1) ans = n;
  printf("%d\n", ans);
  return 0;
}
