// use std::ops::{Index, IndexMut};
// use std::cmp::{Ordering, min, max};
// use std::collections::{BinaryHeap, BTreeMap};
// use std::collections::btree_map::Entry::{Occupied, Vacant};
// use std::clone::Clone;

fn getline() -> String{
    let mut res = String::new();
    std::io::stdin().read_line(&mut res).ok();
    res
}

macro_rules! readl {
    ($t: ty) => {
        {
            let s = getline();
            s.trim().parse::<$t>().unwrap()
        }
    };
    ($( $t: ty),+ ) => {
        {
            let s = getline();
            let mut iter = s.trim().split(' ');
            ($(iter.next().unwrap().parse::<$t>().unwrap(),)*) 
        }
    };
}

macro_rules! readlvec {
    ($t: ty) => {
        {
            let s = getline();
            let iter = s.trim().split(' ');
            iter.map(|x| x.parse().unwrap()).collect::<Vec<$t>>()
        }
    }
}

macro_rules! mvec {
    ($v: expr, $s: expr) => {
        vec![$v; $s]
    };
    ($v: expr, $s: expr, $($t: expr),*) => {
        vec![mvec!($v, $($t),*); $s]
    };
}

macro_rules! debug {
    ($x: expr) => {
        println!("{}: {:?}", stringify!($x), $x)
    }
}

fn printiter<'a, T>(v: &'a T)
where
    &'a T: std::iter::IntoIterator, 
    <&'a T as std::iter::IntoIterator>::Item: std::fmt::Display {
    for (i,e) in v.into_iter().enumerate() {
        if i != 0 {
            print!(" ");
        }
        print!("{}", e);
    }
    println!("");
}

fn gcd(x: u64, y: u64) -> u64 {
    if y == 0 {
        x
    } else {
        gcd(y, x%y)
    }
}

fn lcm(x: u64, y: u64) -> u64 {
    x*y / gcd(x, y)
}

struct Replacement{
    v: Vec<usize>,
}

impl Replacement {
    fn dfs(&self, used: &mut Vec<bool>, p: usize) -> u64 {
        if used[p] {
            0
        } else {
            used[p] = true;
            self.dfs(used, self.v[p])+1
        }
    }
    
    fn get_ord(&self) -> usize {
        let n = self.v.len();
        let mut used = vec![false; n];
        let mut res = 1;
        for i in 0..n {
            let ret = self.dfs(&mut used, i);
            if ret != 0 {
                res = lcm(res, ret);
            }
        }
        res as usize
    }
}

fn main() {
    let n = readl!(usize);
    let k = readl!(usize);
    let mut v: Vec<_> = (0..n).collect();
    for _ in 0..k {
        let (x, y) = readl!(usize, usize);
        v.swap(x-1, y-1);
    }
    // debug!(v);
    let r = Replacement{ v: v };
    println!("{}", r.get_ord());
}