#include <bits/stdc++.h>
using namespace std;
struct EDGE {
  int y;
  int type;
  EDGE* Next;
};
EDGE EPool[200000];
int EPTop = 0;
EDGE* E[111111];
int insert_edge(int x, int y, int type) {
  EDGE* Now = &EPool[EPTop++];
  Now->y = y;
  Now->Next = E[x];
  Now->type = type;
  E[x] = Now;
  return 0;
}
int gcd(int a, int b) {
  if (!b) return a;
  return gcd(b, a % b);
}
int ans = -1;
bool vis[111111];
int visk[111111];
int dfs(int x, int k) {
  if (vis[x]) {
    if (k - visk[x] != 0) {
      if (ans == -1)
        ans = abs(k - visk[x]);
      else
        ans = gcd(ans, abs(k - visk[x]));
    }
    return 0;
  }
  visk[x] = k;
  vis[x] = true;
  for (EDGE* e = E[x]; e; e = e->Next) {
    dfs(e->y, k + e->type);
  }
  return 0;
}
int main(void) {
  int n = 0;
  int m = 0;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int x = 0;
    int y = 0;
    scanf("%d %d", &x, &y);
    insert_edge(x, y, 1);
    insert_edge(y, x, -1);
  }
  for (int i = 1; i <= n; i++)
    if (!vis[i]) dfs(i, 0);
  if (ans == -1) ans = n;
  printf("%d\n", ans);
  while (getchar() != EOF)
    ;
  return 0;
}
