// submissions/63360 + return 0
a[101],x,y,c;gcd(a,b){return b?gcd(b,a%b):a;}main(i){for(gets(gets(&i));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;}