#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n, m, ans;
int val[maxn];
vector<int> adj[maxn], len[maxn];
bool vis[maxn];
int gcd(int a, int b) {
  if (!a || !b) return a + b;
  return gcd(b, a % b);
}
void dfs(int cur, int id) {
  vis[cur] = 1;
  val[cur] = id;
  for (int i = 0; i < adj[cur].size(); i++) {
    int son = adj[cur][i], l = len[cur][i];
    if (!vis[son]) {
      dfs(son, id + l);
    } else if (val[son] != id + l) {
      ans = gcd(ans, abs(id + l - val[son]));
    }
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1, u, v; i <= m; i++) {
    scanf("%d %d", &u, &v);
    adj[u].push_back(v);
    len[u].push_back(1);
    adj[v].push_back(u);
    len[v].push_back(-1);
  }
  for (int i = 1; i <= n; i++)
    if (!vis[i]) dfs(i, 0);
  if (!ans) ans = n;
  return !printf("%d\n", ans);
}
