#include #include using namespace std; typedef long long ll; ll gcd(ll a, ll b) { if (b == 0) return a; else return gcd(b, a % b); } ll lcm(ll a, ll b) { return a / gcd(a, b) * b; } int calc_cycle(int elt, vector& perm, vector& used) { used[elt] = true; int next = perm[elt]; if (used[next]) return 1; else return calc_cycle(next, perm, used) + 1; } int main() { int n, k; cin >> n; vector perm(n); vector used(n, false); for (int i = 0; i < n; i++) { perm[i] = i; } cin >> k; for (int i = 0; i < k; i++) { int x, y; cin >> x >> y; swap(perm[x - 1], perm[y - 1]); } vector cycles; for (int i = 0; i < n; i++) { if (!used[i]) { cycles.push_back(calc_cycle(i, perm, used)); } } ll ans = 1; for (auto cycle : cycles) { ans = lcm(ans, cycle); } cout << ans << endl; return 0; }