origin=[i for i in range(int(input()))]
rule=origin[:]
for i in range(int(input())):
    x,y=map(lambda n:int(n)-1,input().split())
    rule[x],rule[y]=rule[y],rule[x]
ans=1
before=origin[:]
after=origin[:]
while ans<10:
    i=0
    for j in rule:
        after[i]=before[j]
        i+=1
    if origin==after:
        print(ans)
        break
    before=after[:]
    ans+=1