// submissions/63360 - gets(&i)
a[101],x,y,c;
gcd(a,b){return b?gcd(b,a%b):a;}
main(i){
	for(scanf("%d%d",&x,&y);i=~scanf("%d%d",&x,&y);a[y]=a[x]?a[x]:x,a[x]=i)i=a[y]?a[y]:y;
	for(x=1;a[++i];x*=c/gcd(x,c))for(c=1,y=a[i];y-i;c++)y=a[y];
	x=!printf("%d",x);
	return 0;
}