#1197231 (Rust) No.101 ぐるぐる！あみだくじ！

• 問題: No.101 ぐるぐる！あみだくじ！
• ユーザー: matajupi
• 提出日時: 2026-11-06 13:25:16
• 言語: Rust (1.99.1 + proconio + num + itertools + ACL)
• 結果: AC
• 実行時間: 0 ms / 5,000 ms
• コード長: 10,637 bytes
• コンパイル時間: 1,116 ms
• コンパイル使用メモリ: 203,016 KB
• 実行使用メモリ: 9,924 KB
• 最終ジャッジ日時: 2026-11-06 13:25:21
• 合計ジャッジ時間: 3,228 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge7_0

ファイルパターン	結果
sample	AC * 3
other	AC * 37

ソースコード

// Reference: https://github.com/matajupi/matajupilib_snippets

// 　∧＿∧
// （｡･ﻌ･｡)つ━☆・*。
// ⊂　　 ノ 　　　✧・゜+.
// 　しーＪ　　　°。+ *´¨)
// 　　　　　　　　　.· ´¸.·´¨) ¸.·¨)
// 　　　　　　　　　　(¸.·´ ✧(¸.·’*✧

#![allow(dead_code, unused_imports, unused_macros, unexpected_cfgs)]

#[macro_use]
mod matajupilib {
    use crate::*;

    // =============================================================================
    // Macros
    // =============================================================================
    macro_rules! chmin {
        ($a:expr, $b:expr) => {
            if $b < $a {
                $a = $b;
                true
            } else {
                false
            }
        };
    }

    macro_rules! chmax {
        ($a:expr, $b:expr) => {
            if $b > $a {
                $a = $b;
                true
            } else {
                false
            }
        };
    }

    macro_rules! r {
        ($num:expr, $den:expr) => {
            Rational64::new($num, $den)
        };
    }

    /// Debug print macro (Only works in Debug builds; ignored in Release builds)
    macro_rules! d {
        ($($a:expr),* $(,)?) => {
            #[cfg(debug_assertions)]
            eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
        };
    }

    // =============================================================================
    // Constants & Type Aliases
    // =============================================================================
    pub const IINF: i64 = 4_000_000_000_000_000_000;
    pub const UINF: usize = 1_000_000_000;

    pub const DX4: [i64; 4] = [1, 0, -1, 0];
    pub const DY4: [i64; 4] = [0, 1, 0, -1];
    pub const DX8: [i64; 8] = [1, 1, 0, -1, -1, -1, 0, 1];
    pub const DY8: [i64; 8] = [0, 1, 1, 1, 0, -1, -1, -1];

    pub type MinHeap<T> = BinaryHeap<R<T>>;
    pub type MaxHeap<T> = BinaryHeap<T>;

    // =============================================================================
    // Type Cast Traits
    // =============================================================================
    macro_rules! define_cast_trait {
        ($trait_name:ident, $fn_name:ident, $target_type:ty, $($source_type:ty),*) => {
            pub trait $trait_name {
                fn $fn_name(self) -> $target_type;
            }
            $(
                impl $trait_name for $source_type {
                    #[inline]
                    fn $fn_name(self) -> $target_type { self as $target_type }
                }
            )*
        };
    }

    define_cast_trait!(
        AsUsize, u, usize, i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize, char,
        f32, f64
    );
    define_cast_trait!(
        AsI64, i, i64, i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize, char, f32,
        f64
    );
    define_cast_trait!(
        AsF64, f, f64, i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize, f32, f64
    );
    define_cast_trait!(
        AsI128, l, i128, i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize, char, f32,
        f64
    );

    pub trait AsMint {
        fn m(self) -> Mint;
    }

    impl<T> AsMint for T
    where
        T: Into<Mint>,
    {
        #[inline]
        fn m(self) -> Mint {
            self.into()
        }
    }

    // =============================================================================
    // Helper Traits
    // =============================================================================
    pub trait Unwrapper<T> {
        fn uw(self) -> T;
        fn uwor(self, default: T) -> T;
        fn uworelse<F>(self, f: F) -> T
        where
            F: FnOnce() -> T;
    }

    impl<T> Unwrapper<T> for Option<T> {
        #[inline]
        fn uw(self) -> T {
            self.expect("None value")
        }
        #[inline]
        fn uwor(self, default: T) -> T {
            self.unwrap_or(default)
        }
        #[inline]
        fn uworelse<F>(self, f: F) -> T
        where
            F: FnOnce() -> T,
        {
            self.unwrap_or_else(f)
        }
    }

    impl<T, E: std::fmt::Debug> Unwrapper<T> for Result<T, E> {
        #[inline]
        fn uw(self) -> T {
            self.expect("Err value")
        }
        #[inline]
        fn uwor(self, default: T) -> T {
            self.unwrap_or(default)
        }
        #[inline]
        fn uworelse<F>(self, f: F) -> T
        where
            F: FnOnce() -> T,
        {
            self.unwrap_or_else(|_| f())
        }
    }

    pub trait ShortNumOps: Sized {
        fn sadd(self, rhs: Self) -> Self;
        fn ssub(self, rhs: Self) -> Self;
        fn smul(self, rhs: Self) -> Self;
        fn oadd(self, rhs: Self) -> (Self, bool);
        fn osub(self, rhs: Self) -> (Self, bool);
        fn omul(self, rhs: Self) -> (Self, bool);
    }

    macro_rules! impl_short_num_ops {
        ($($t:ty),*) => { $(
            impl ShortNumOps for $t {
                #[inline] fn sadd(self, rhs: Self) -> Self { self.saturating_add(rhs) }
                #[inline] fn ssub(self, rhs: Self) -> Self { self.saturating_sub(rhs) }
                #[inline] fn smul(self, rhs: Self) -> Self { self.saturating_mul(rhs) }
                #[inline] fn oadd(self, rhs: Self) -> (Self, bool) { self.overflowing_add(rhs) }
                #[inline] fn osub(self, rhs: Self) -> (Self, bool) { self.overflowing_sub(rhs) }
                #[inline] fn omul(self, rhs: Self) -> (Self, bool) { self.overflowing_mul(rhs) }
            }
        )* };
    }
    impl_short_num_ops!(
        i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize
    );

    pub trait MapExt<K, V> {
        fn orins(&mut self, key: K, default: V) -> &mut V;
        fn ordef(&mut self, key: K) -> &mut V
        where
            V: Default;
        fn orwith<F: FnOnce() -> V>(&mut self, key: K, f: F) -> &mut V;
    }

    impl<K: Eq + Hash, V, S: BuildHasher> MapExt<K, V> for HashMap<K, V, S> {
        #[inline]
        fn orins(&mut self, key: K, default: V) -> &mut V {
            self.entry(key).or_insert(default)
        }
        #[inline]
        fn ordef(&mut self, key: K) -> &mut V
        where
            V: Default,
        {
            self.entry(key).or_default()
        }
        #[inline]
        fn orwith<F: FnOnce() -> V>(&mut self, key: K, f: F) -> &mut V {
            self.entry(key).or_insert_with(f)
        }
    }

    impl<K: Ord, V> MapExt<K, V> for BTreeMap<K, V> {
        #[inline]
        fn orins(&mut self, key: K, default: V) -> &mut V {
            self.entry(key).or_insert(default)
        }
        #[inline]
        fn ordef(&mut self, key: K) -> &mut V
        where
            V: Default,
        {
            self.entry(key).or_default()
        }
        #[inline]
        fn orwith<F: FnOnce() -> V>(&mut self, key: K, f: F) -> &mut V {
            self.entry(key).or_insert_with(f)
        }
    }

    pub trait StrExt {
        fn cv(&self) -> Vec<char>;
    }

    impl StrExt for str {
        #[inline]
        fn cv(&self) -> Vec<char> {
            self.chars().collect()
        }
    }

    // =============================================================================
    // Iterator Extensions
    // =============================================================================
    pub trait IntoIterExt: IntoIterator + Sized {
        #[inline]
        fn iit(self) -> Self::IntoIter {
            self.into_iter()
        }
        #[inline]
        fn col<B: FromIterator<Self::Item>>(self) -> B {
            self.into_iter().collect()
        }
        #[inline]
        fn colv(self) -> Vec<Self::Item> {
            self.into_iter().collect()
        }
    }
    impl<T: IntoIterator> IntoIterExt for T {}

    pub trait IterExt {
        #[inline]
        fn it(&self) -> <&Self as IntoIterator>::IntoIter
        where
            for<'a> &'a Self: IntoIterator,
        {
            self.into_iter()
        }
        #[inline]
        fn itm(&mut self) -> <&mut Self as IntoIterator>::IntoIter
        where
            for<'a> &'a mut Self: IntoIterator,
        {
            self.into_iter()
        }
    }
    impl<T: ?Sized> IterExt for T {}

    // =============================================================================
    // Scanner
    // =============================================================================
    use std::io::Read;

    pub struct Scanner {
        iter: std::vec::IntoIter<String>,
    }

    impl Scanner {
        pub fn new() -> Self {
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            Self {
                iter: s.split_whitespace().map(|s| s.to_string())
                    .collect::<Vec<_>>().into_iter(),
            }
        }
        pub fn n<T: std::str::FromStr>(&mut self) -> T {
            self.iter.next().unwrap().parse().ok().unwrap()
        }
        pub fn ns<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.n()).collect()
        }
    }
}

// =============================================================================
// Imports & Main
// =============================================================================
// AtCoder
// use amplify::*;
// use omniswap::swap;
// use ordered_float::OrderedFloat as OF;
// use rand::Rng;
// use superslice::Ext;

// yukicoder
use ::num::{integer::*, rational::*, *};
use itertools::Itertools;
use ac_library::*;
use proconio::{marker::*, *};

// Other
use std::cmp::{Reverse as R, *};
use std::collections::{HashMap as Map, HashSet as Set, *};
use std::f64::consts::*;
use std::hash::{BuildHasher, Hash};
use std::mem::*;
use std::ops::{Range, RangeBounds};

// AtCoder, yukicoder
use ac_library::ModInt998244353 as Mint;
// Other
// type Mint = i64;

use matajupilib::*;

fn solve() {
    input! {
        n: usize,
        k: usize,
        xy: [(Usize1, Usize1); k],
    };

    let mut to = (0..n).colv();
    for i in 0..k {
        let (x, y) = xy[i];
        let t = to[x];
        to[x] = to[y];
        to[y] = t;
    }

    let mut vis = vec![false; n];
    let mut res = 1;
    for i in 0..n {
        if !vis[i] {
            let mut cnt = 0;
            let mut cur = i;
            while !vis[cur] {
                vis[cur] = true;
                cur = to[cur];
                cnt += 1;
            }
            res = lcm(res, cnt);
        }
    }
    println!("{}", res);
}

fn main() {
    let t = 1;
    for _ in 0..t {
        solve();
    }
}