#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:64000000")
using namespace std;
struct Edge {
  int u, v, d;
};
bool used[100005];
int d[100005];
vector<Edge> g[100005];
int n, m;
int cur;
int gcd(int x, int y) {
  if (!y) return x;
  return gcd(y, x % y);
}
void dfs(int u, int c) {
  used[u] = true;
  d[u] = c;
  for (int i = 0; i < (int)(g[u].size()); i++) {
    int v = g[u][i].v;
    if (used[v] && g[u][i].d == 1) {
      cur = gcd(abs(d[u] + 1 - d[v]), cur);
    }
    if (!used[v]) {
      dfs(v, c + g[u][i].d);
    }
  }
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < (int)(m); i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    x--, y--;
    Edge xy = {x, y, 1};
    Edge yx = {y, x, -1};
    g[x].push_back(xy);
    g[y].push_back(yx);
  }
  int k = 0;
  for (int i = 0; i < (int)(n); i++) {
    if (!used[i]) {
      cur = 0;
      dfs(i, 0);
      k = gcd(cur, k);
    }
  }
  if (k == 0) k = n;
  cout << k << endl;
  return 0;
}
