## solution

$$\begin{matrix} \vdots & \vdots & \vdots & & \vdots \\ 0 & 1 & 2 & \dots & N - 1 \\ N & N + 1 & N + 2 & \dots & 2N - 1 \\ 2N & 2N + 1 & 2N + 2 & \dots & 3N - 1 \\ 3N & 3N + 1 & 3N + 2 & \dots & 4N - 1 \\ \vdots & \vdots & \vdots & & \vdots \end{matrix}$$

## implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
using namespace std;
template <typename T> T gcd(T a, T b) { while (a) { b %= a; swap(a, b); } return b; }

int main() {
// input
int n; cin >> n;
int m; cin >> m;
vector<vector<int> > fwd(n);
vector<vector<int> > bck(n);
REP (i, m) {
int a, b; cin >> a >> b;
fwd[a].push_back(b);
bck[b].push_back(a);
}

// solve
vector<int> used(n, INT_MAX);
int cycle;
function<void (int, int)> go = [&](int a, int k) {
if (used[a] != INT_MAX) {
int c = abs(used[a] - k);
if (c != 0) {
if (cycle == INT_MAX) {
cycle = c;
} else {
cycle = gcd(cycle, c);
}
}
} else {
used[a] = k;
for (int b : fwd[a]) {
go(b, k + 1);
}
for (int z : bck[a]) {
go(z, k - 1);
}
}
};
REP (a, n) if (used[a] == INT_MAX) {
cycle = INT_MAX;
go(a, 0);
if (cycle == INT_MAX) {