#include<bits/stdc++.h>
using namespace std;
long long n,m,a[101001],x,y;
bool v[100100];
long long gcd(long long a,long long b){
	while(b!=0){
		long long temp=b;
		b=a%b;
		a=temp;
	}
}
long long lcm(long a,long b)
{
	return (a/gcd(a,b))*b;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		a[i]=i;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		swap(a[x],a[y]);
	}
	long long result=1;
	for(int i=1;i<=n;i++)
	{
			if(!v[i])
			{
				int clen=0;
				int j=i;
				while(!v[j])
				{
					v[j]=true;
					j=a[j];
					clen++;
				}
				if(clen>0){
					result=lcm(result,clen);
				}	
			}
	}
	cout<<result<<endl;
	return 0;
}