#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric>
using namespace std;
inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }

int main() {
    int n, k; cin >> n >> k;
    vector<int> nxt(n); iota(nxt.begin(), nxt.end(), 0);
    while (k--) {
        int a, b; cin >> a >> b; a--, b--;
        swap(nxt[a], nxt[b]);
    }
    long long res = 1;
    for (int i = 0; i < n; i++) {
        int cnt = 0;
        for (int x = i; !cnt || x != i; x = nxt[x]) cnt++;
        res = lcm(res, cnt);
    }
    cout << res << endl;
    return 0;
}