import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[] sig = new int[n]; for(int i = 0; i < n; i++) { sig[i] = i; } for(int i = 0; i < k; i++) { int x = sc.nextInt() - 1; int y = sc.nextInt() - 1; sig[x] = sig[y]; sig[y] = sig[x]; } int[] sig2 = new int[n]; for(int i = 0; i < n; i++) { sig2[sig[i]] = i; } int[] b = new int[n]; for(int i = 0; i < n; i++) { int t = 1; int p = i; while(sig2[p] != i) { t++; p = sig2[p]; } b[i] = t; } long lcm = 1; for(int i = 0; i < n; i++) { long g = gcd(lcm, (long)b[i]); lcm = g * (lcm / g) * ((long)b[i] / g); } System.out.println(lcm); } public static long gcd(long a, long b) { if(b == 0) return a; return gcd(b, (a % b)); } }