#include <bits/stdc++.h>
using namespace std;
int st[100010], aim[100010 << 1], nxt[100010 << 1], ln;
int w[100010 << 1];
int tag[100010];
int f[100010];
int n, m;
int ans;
void in_edge(int x, int y, int z) {
  aim[ln] = y;
  nxt[ln] = st[x];
  w[ln] = z;
  st[x] = ln++;
}
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
void dfs(int x) {
  tag[x] = 1;
  for (int i = st[x]; i != -1; i = nxt[i]) {
    int v = aim[i];
    if (!tag[v]) {
      f[v] = f[x] + w[i];
      dfs(v);
    } else {
      int value = abs(f[v] - (f[x] + w[i]));
      if (value) {
        if (ans == -1)
          ans = value;
        else
          ans = gcd(ans, value);
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  memset(st, -1, sizeof(st));
  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    in_edge(u, v, 1);
    in_edge(v, u, -1);
  }
  ans = -1;
  for (int i = 1; i <= n; i++)
    if (!tag[i]) {
      f[i] = 0;
      dfs(i);
    }
  if (ans == -1) ans = n;
  printf("%d\n", ans);
  return 0;
}
