#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
inline int gcd(int a, int b) {
  while (b) a %= b, swap(a, b);
  return a;
}
int ans;
int n, m;
struct Edge {
  int to, dist, nxt;
} e[maxn << 1];
int first[maxn];
int rd[maxn];
inline void add_edge(int from, int to) {
  static int cnt = 0;
  e[++cnt].nxt = first[from];
  first[from] = cnt;
  e[cnt].to = to;
  e[cnt].dist = 1;
  e[++cnt].nxt = first[to];
  first[to] = cnt;
  e[cnt].to = from;
  e[cnt].dist = -1;
}
int tim[maxn];
bool vis[maxn];
inline void dfs(int now) {
  vis[now] = true;
  for (int i = first[now]; i; i = e[i].nxt) {
    int to = e[i].to;
    if (vis[to])
      ans = gcd(ans, abs((tim[now] + e[i].dist) - tim[to]));
    else
      tim[to] = tim[now] + e[i].dist, dfs(to);
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, f, t; i <= m; ++i) {
    scanf("%d%d", &f, &t);
    add_edge(f, t);
  }
  for (int i = 1; i <= n; ++i)
    if (!vis[i]) dfs(i);
  printf("%d\n", ans ? ans : n);
  return 0;
}
