n = int(input())
k = int(input())

r = list(range(n))
for _ in range(k):
    x,y = map(int,input().split())
    r[x-1],r[y-1] = r[y-1],r[x-1]

from math import gcd
def lcm(x,y): return x//gcd(x,y)*y

ans = 1
used = [0]*n
for i in range(n):
    if used[i]: continue
    cnt = 0
    while used[i]==0:
        used[i] = 1
        i = r[i]
        cnt += 1
    ans = lcm(ans,cnt)

print(ans)