#include "bits/stdc++.h" using namespace std; #define REP(i, n) for(int i=0; i<(n); i++) int gcd(int a, int b) { if (!b) return a; return gcd(b, a%b); } int lcm(int a, int b) { return a / gcd(a, b) * b; } int N,K; signed main() { cin >> N>>K; vector amida(N); REP(i,N) amida[i] = i; int x, y; REP(i,K) { cin >> x >> y; swap(amida[x-1], amida[y-1]); } int cnt = 0; vector tmp(N); vector loop(N, 0); REP(i,N) tmp[i] = i; while(true) { cnt++; vector tmp2(N); REP(i,N) { tmp2[i] = tmp[amida[i]]; } bool isok = true; REP(i,N) { if (loop[i] == 0 && tmp2[i] == i) { loop[i] = cnt; } if (loop[i] == 0) isok = false; } if (isok) break; tmp = tmp2; } // 最小公倍数を求める int lcmc = 1; REP(i,N) { lcmc = lcm(lcmc, loop[i]); } cout << lcmc << endl; return 0; }