import numpy 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 1: i=0 for j in rule: after[i]=before[j] i+=1 if origin==after: print(ans) break before=after[:] ans+=1