// https://atcoder.jp/contests/abc393/tasks/abc393_b

fn run(s: &str) -> usize {
    let chars: Vec<char> = s.chars().collect();
    let mut ans = 0;

    for i in 0..s.len() {
        for j in i+1..s.len() {
            for k in j+1..s.len() {
                if j - i == k - j {
                    if chars[i] == 'A' && chars[j] == 'B' && chars[k] == 'C' {
                        ans += 1;
                    }
                }
            }
        }
    }

    ans
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(&'static str, usize);

    #[test]
    fn test() {
        let tests = [
            TestCase("AABCC", 2),
            TestCase("ARC", 0),
            TestCase("AABAAABBAEDCCCD", 4),
        ];

        for TestCase(s, expected) in tests {
            assert_eq!(run(s), expected);
        }
    }
}

// https://atcoder.jp/contests/abc331/tasks/abc331_b

fn run(n: usize, s: usize, m: usize, l: usize) -> usize {
    let mut ans = std::usize::MAX;

    for i in 0..=100 {
        for j in 0..=100 {
            for k in 0..=100 {
                if i*6 + j*8 + k*12 >= n {
                    ans = ans.min(i*s + j*m + k*l);
                }
            }
        }
    }

    ans
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(300, run(16, 120,  150, 200));
        assert_eq!(10, run(10, 100, 50, 10));
        assert_eq!(10000, run(99, 600, 800, 1200));
    }
}

// https://atcoder.jp/contests/abc224/tasks/abc224_c

fn run(n: usize, xy: Vec<(isize, isize)>) -> usize {
    let mut ans = 0;

    for i in 0..n {
        for j in i+1..n {
            for k in j+1..n {
                if (xy[j].0 - xy[i].0)*(xy[k].1 - xy[i].1) - (xy[k].0 - xy[i].0)*(xy[j].1 - xy[i].1) != 0 {
                    ans += 1;
                }
            }
        }
    }

    ans
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(usize, Vec<(isize, isize)>, usize);

    #[test]
    fn test() {
        let tests = [
            TestCase(4, vec![(0, 1), (1, 3), (1, 1), (-1, -1)], 3),
            TestCase(20, vec![(224, 433), (987654321, 987654321), (2, 0), (6, 4), (314159265, 358979323), (0, 0), (-123456789, 123456789), (-1000000000, 1000000000), (124, 233), (9, -6), (-4, 0), (9, 5), (-7, 3), (333333333, -333333333), (-9, -1), (7, -10), (-1, 5), (324, 633), (1000000000, -1000000000), (20, 0)], 1124),
        ];

        for TestCase(n, xy, expected) in tests {
            assert_eq!(run(n, xy), expected);
        }
    }
}

// https://atcoder.jp/contests/abc391/tasks/abc391_b

fn run(n: usize, m: usize, s: Vec<&str>, t: Vec<&str>) -> (usize, usize) {
    let vec_s: Vec<Vec<char>> = s.into_iter().map(|s| s.chars().collect()).collect();
    let vec_t: Vec<Vec<char>> = t.into_iter().map(|s| s.chars().collect()).collect();

    for i in 0..=n-m {
        for j in 0..=n-m {
            let mut flag = true;

            for k in 0..m {
                for l in 0..m {
                    if vec_s[i+k][j+l] != vec_t[k][l] {
                        flag = false;
                    }
                }
            }

            if flag {
                return (i+1, j+1);
            }
        }
    }

    unreachable!();
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(usize, usize, Vec<&'static str>, Vec<&'static str>, (usize, usize));

    #[test]
    fn test() {
        let tests = [
            TestCase(3, 2, vec!["#.#", "..#", "##."], vec![".#", "#."], (2, 2)),
            TestCase(2, 1, vec!["#.", "##"], vec!["."], (1, 2)),
        ];

        for TestCase(n, m, s, t, expected) in tests {
            assert_eq!(run(n, m, s, t), expected);
        }
    }
}

// https://atcoder.jp/contests/abc201/tasks/abc201_c

fn run(s: &str) -> usize {
    let chars: Vec<char> = s.chars().collect();

    let mut ans = 0;

    for i in 0..10000 {
        let str = format!("{:04}", i);

        let mut flags = vec![false; 10];

        for c in str.chars() {
            let i = c.to_digit(10).unwrap();

            flags[i as usize] = true;
        }

        let mut flag = true;

        for j in 0..10 {
            if chars[j] == 'o' && flags[j] == false {
                flag = false;
                break;
            }

            if chars[j] == 'x' && flags[j] {
                flag = false;
                break;
            }
        }

        if flag {
            ans += 1;
        }
    }

    ans
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(&'static str, usize);

    #[test]
    fn test() {
        let tests = [
            TestCase("ooo???xxxx", 108),
            TestCase("o?oo?oxoxo", 0),
            TestCase("xxxxx?xxxo", 15),
        ];

        for TestCase(s, expected) in tests {
            assert_eq!(run(s), expected);
        }
    }
}

// https://atcoder.jp/contests/joi2024yo2/tasks/joi2024_yo2_a

fn run(_n: usize, a: Vec<usize>) -> &'static str {
    let mut vec = vec![false; 200_000];

    for i in a {
        vec[i-1] = true;
    }

    for i in 0..200_000-3 {
        if vec[i] == true && vec[i+3] == true && vec[i+6] == true {
            return "Yes";
        }
    }

    "No"
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(usize, Vec<usize>, &'static str);

    #[test]
    fn test() {
        let tests = [
            TestCase(3, vec![2, 5, 8], "Yes"),
            TestCase(4, vec![1, 4, 6, 4], "No"),
            TestCase(8, vec![9, 8, 11, 1, 1, 6, 10, 4], "No"),
            TestCase(20, vec![2, 15, 4, 30, 6, 8, 11, 27, 14, 3, 16, 26, 19, 2, 23, 21, 18, 13, 28, 6], "Yes"),
        ];

        for TestCase(n, a, expected) in tests {
            assert_eq!(run(n, a), expected);
        }
    }
}

// https://atcoder.jp/contests/joi2023yo2/tasks/joi2023_yo2_a

use itertools::Itertools;

fn run(_n: usize, a: Vec<isize>) -> Vec<usize> {
    let vec: Vec<isize> = a.clone().into_iter().sorted().collect();

    let min = vec.iter().min().unwrap();
    let max = vec.iter().max().unwrap();

    a.into_iter()
        .map(|i| {
            std::cmp::max((i - *min).abs(), (*max - i).abs()) as usize
        })
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(usize, Vec<isize>, Vec<usize>);

    #[test]
    fn test() {
        let tests = [
            TestCase(3, vec![13, 15, 20], vec![7, 5, 7]),
            TestCase(2, vec![100, 100], vec![0, 0]),
            TestCase(10, vec![440894064, 101089692, 556439322, 34369336, 98417847, 216265879, 623843484, 554560874, 247445405, 718003331], vec![406524728, 616913639, 522069986, 683633995, 619585484, 501737452, 589474148, 520191538, 470557926, 683633995]),
        ];

        for TestCase(n, a, expected) in tests {
            assert_eq!(run(n, a), expected);
        }
    }
}

// https://atcoder.jp/contests/abc085/tasks/abc085_c

fn run(n: isize, y: isize) -> Vec<isize> {
    for i in 0..=n {
        for j in 0..=n {
            let k = n - i - j;

            if k < 0 || n < k {
                continue;
            }

            if i * 10000 + j * 5000 + k * 1000 == y {
                return vec![i, j, k];
            }
        }
    }

    vec![-1, -1, -1]
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(isize, isize, Vec<isize>);

    #[test]
    fn test() {
        let tests = [
            TestCase(9, 45000, vec![4, 0, 5]),
            TestCase(20, 196000, vec![-1, -1, -1]),
            TestCase(1000, 1234000, vec![2, 54, 944]),
            TestCase(2000, 20000000, vec![2000, 0, 0]),
        ];

        for TestCase(n, y, expected) in tests {
            assert_eq!(run(n, y), expected);
        }
    }
}

// https://atcoder.jp/contests/abc264/tasks/abc264_d

fn run(s: &str) -> usize {
    let mut ans = 0;

    let mut vec: Vec<usize> = s.chars()
        .map(|c| {
            match c {
                'a' => 0,
                't' => 1,
                'c' => 2,
                'o' => 3,
                'd' => 4,
                'e' => 5,
                'r' => 6,
                _ => unreachable!(),
            }
        })
        .collect();

    for i in 0..7 {
        let mut flag = true;

        for j in 0..7-i-1 {
            if vec[j] > vec[j+1] {
                vec.swap(j, j+1);
                ans += 1;
                flag = false;
            }
        }

        if flag == true {
            return ans;
        }
    }

    ans
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(&'static str, usize);

    #[test]
    fn test() {
        let tests = [
            TestCase("catredo", 8),
            TestCase("atcoder", 0),
            TestCase("redocta", 21),
        ];

        for TestCase(s, expected) in tests {
            assert_eq!(run(s), expected);
        }
    }
}

use std::cmp::Ordering;

fn upper_bound<T: Ord>(vec: &[T], value: T) -> usize {
    vec.binary_search_by(|x| {
        if *x <= value {
            Ordering::Less
        } else {
            Ordering::Greater
        }
    })
    .err()
    .unwrap()
}

fn run(_n: usize, a: Vec<usize>) -> usize {
    a.iter()
        .map(|x| {
            upper_bound(&a, x/2)
        })
        .sum()
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(usize, Vec<usize>, usize);

    #[test]
    fn test() {
        let tests = [
            TestCase(6, vec![2, 3, 4, 4, 7, 10], 8),
            TestCase(3, vec![387, 388, 389], 0),
            TestCase(32, vec![1, 2, 4, 5, 8, 10, 12, 16, 19, 25, 33, 40, 50, 64, 87, 101, 149, 175, 202, 211, 278, 314, 355, 405, 412, 420, 442, 481, 512, 582, 600, 641], 388),
        ];

        for TestCase(n, a, expected) in tests {
            assert_eq!(run(n, a), expected);
        }
    }
}

// https://atcoder.jp/contests/abc365/tasks/abc365_c

use std::cmp::min;

fn check(a: &Vec<usize>, x: usize, m: usize) -> bool {
    let mut total = 0;

    for n in a.iter() {
        total += min(n, &x);
    }

    total <= m
}

fn run(_n: usize, m: usize, a: Vec<usize>) -> String {
    let sum: usize = a.iter().sum();

    if sum <= m {
        return "infinite".to_string();
    }

    let mut l = 0;
    let mut r = std::usize::MAX;

    while l+1 < r {
        let tmp = (l+r)/2;

        if check(&a, tmp, m) == true {
            l = tmp;
        } else {
            r = tmp;
        }
    }

    l.to_string()
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(usize, usize, Vec<usize>, &'static str);

    #[test]
    fn test() {
        let tests = [
            TestCase(4, 8, vec![1, 3, 2, 4], "2"),
            TestCase(3, 20, vec![5, 3, 2], "infinite"),
            TestCase(10, 23, vec![2, 5, 6, 5, 2, 1, 7, 9, 7, 2], "2"),
        ];

        for TestCase(n, m, a, expected) in tests {
            assert_eq!(run(n, m, a), expected);
        }
    }
}

// https://atcoder.jp/contests/abc180/tasks/abc180_c

fn run(n: usize) -> Vec<usize> {
    let mut ans = Vec::new();

    for i in 1..=(n as f64).sqrt() as usize {
        if n % i == 0 {
            let j = n / i;

            ans.push(i);

            if i != j {
                ans.push(j);
            }
        }
    }

    ans.sort();

    ans
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(vec![1, 2, 3, 6], run(6));
        assert_eq!(vec![1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 36, 40, 45, 48, 60, 72, 80, 90, 120, 144, 180, 240, 360, 720], run(720));
        assert_eq!(vec![1, 1000000007], run(1000000007));
        assert_eq!(vec![1], run(1));
    }
}

// https://atcoder.jp/contests/arc105/tasks/arc105_a

fn run(a: usize, b: usize, c: usize, d: usize) -> String {
    let vec = vec![a, b, c, d];

    for bit in 0..(1 << 4) {
        let mut eat = 0;
        let mut rest = 0;

        for i in 0..4 {
            if bit & (1 << i) != 0 {
                eat += vec[i];
            } else {
                rest += vec[i];
            }
        }

        if eat == rest {
            return String::from("Yes");
        }
    }

    String::from("No")
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(String::from("Yes"), run(1, 3, 2, 4));
        assert_eq!(String::from("No"), run(1, 2, 4, 8));
        assert_eq!(String::from("Yes"), run(1, 1, 1, 1));
        assert_eq!(String::from("Yes"), run(1, 100, 50, 51));
        assert_eq!(String::from("Yes"), run(2, 100, 48, 50));
        assert_eq!(String::from("Yes"), run(63214004, 4741111, 4654151, 63300964));
        assert_eq!(String::from("No"), run(4630987, 9157337, 18793476, 5005153));
        assert_eq!(String::from("No"), run(93407609, 30427494, 56229544, 81174201));
    }
}

// https://atcoder.jp/contests/arc025/tasks/arc025_1

fn run(dd: Vec<usize>, jj: Vec<usize>) -> usize {
    let mut ans = 0;

    for bit in 0..(1 << dd.len()) {
        let mut total = 0;

        for i in 0..dd.len() {
            if bit & (1 << i) != 0 {
                total += dd[i];
            } else {
                total += jj[i];
            }
        }

        ans = ans.max(total);
    }

    ans
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(33, run(vec![4, 2, 0, 5, 6, 2, 5], vec![6, 1, 4, 3, 6, 4, 6]));
        assert_eq!(35, run(vec![1, 2, 3, 4, 5, 6, 7], vec![2, 3, 4, 5, 6, 7, 8]));
        assert_eq!(0, run(vec![0, 0, 0, 0, 0, 0, 0], vec![0, 0, 0, 0, 0, 0, 0]));
        assert_eq!(793, run(vec![8, 3, 0, 2, 5, 25, 252], vec![252, 252, 2, 5, 2, 5, 2]));
    }
}

// https://atcoder.jp/contests/abc374/tasks/abc374_c

use std::cmp::{min, max};

fn run(n: usize, k: Vec<usize>) -> usize {
    let mut ans = std::usize::MAX;

    for bit in 0..(1 << n) {
        let mut left = 0;
        let mut right = 0;

        for i in 0..n {
            if bit & 1 << i != 0 {
                left += k[i];
            } else {
                right += k[i];
            }
        }

        ans = min(ans, max(left ,right));
    }

    ans
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(usize, Vec<usize>, usize);

    #[test]
    fn test() {
        let tests = [
            TestCase(5, vec![2, 3, 5, 10, 12], 17),
            TestCase(2, vec![1, 1], 1),
            TestCase(6, vec![22, 25, 26, 45, 22, 31], 89),
        ];

        for TestCase(n, k, expected) in tests {
            assert_eq!(run(n, k), expected);
        }
    }
}

// https://atcoder.jp/contests/abc182/tasks/abc182_c

fn run(n: usize) -> i32 {
    // 1個も消さずに3で割り切れる場合
    if n % 3 == 0 {
        return 0;
    }

    let mut ans = std::i32::MAX;
    // 各桁をVec<i32>に格納
    let vec: Vec<i32> = n.to_string().chars().map(|c| c.to_digit(10).unwrap() as i32).collect();

    for bit in 1..(1 << vec.len()) {
        // 各桁の合計数
        let mut num = 0;

        // 数値を消した数
        let mut count = 0;

        for i in 0..vec.len() {
            if bit & (1 << i) != 0 {
                num += vec[i] * 10_i32.pow(i as u32);
                count += 1;
            }
        }

        if num % 3 == 0 {
            ans = ans.min(count);
        }
    }

    if ans == std::i32::MAX {
        -1
    } else {
        ans
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(1, run(35));
        assert_eq!(0, run(369));
        assert_eq!(1, run(6227384));
        assert_eq!(-1, run(11));
    }
}

// https://atcoder.jp/contests/abc079/tasks/abc079_c

fn run(s: &str) -> String {
    let nums: Vec<i32> = s.chars().map(|c| c.to_digit(10).unwrap() as i32).collect();

    for bit in 0..(1 << 3) {
        // +、-を格納していくVec<char>
        let mut ans = Vec::new();
        // 各数値を+-した合計値
        let mut sum = nums[0];

        for i in 0..3 {
            if bit & (1 << i) != 0 {
                sum += nums[i+1];
                ans.push('+');
            } else {
                sum -= nums[i+1];
                ans.push('-');
            }
        }

        if sum == 7 {
            return format!("{}{}{}{}{}{}{}=7", nums[0], ans[0], nums[1], ans[1], nums[2], ans[2], nums[3]);
        }
    }

    unreachable!();
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(String::from("1+2+2+2=7"), run("1222"));
        assert_eq!(String::from("0-2+9-0=7"), run("0290"));
        assert_eq!(String::from("3+2+4-2=7"), run("3242"));
    }
}

// https://atcoder.jp/contests/abc045/tasks/arc061_a

fn run(s: &str) -> usize {
    let len = s.len();
    let chars: Vec<char> = s.chars().collect();

    let mut ans = 0;

    for bit in 0..(1 << len-1) {
        let mut current = chars[0].to_string();
        let mut sum = 0;

        for i in 0..(len-1) {
            if bit & (1 << i) != 0 {
                current.push(chars[i+1]);
            } else {
                sum += current.parse::<usize>().unwrap();
                current = chars[i+1].to_string();
            }
        }

        sum += current.parse::<usize>().unwrap();
        ans+= sum;
    }

    ans
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(&'static str, usize);

    #[test]
    fn test() {
        let tests = [
            TestCase("125", 176),
            TestCase("9999999999", 12656242944),
        ];

        for TestCase(s, expected) in tests {
            assert_eq!(run(s), expected);
        }
    }
}

// https://atcoder.jp/contests/abc229/tasks/abc229_b

fn calc(a: usize, b: usize) -> bool {
    if a == 0 || b == 0 {
        true
    } else if a%10 + b %10 >= 10 {
        false
    } else {
        calc(a/10, b/10)
    }
}

fn run(a: usize, b: usize) -> String {
    if calc(a, b) == true {
        String::from("Easy")
    } else {
        String::from("Hard")
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(String::from("Hard"), run(229, 390));
        assert_eq!(String::from("Easy"), run(123456789, 9876543210));
    }
}

// https://atcoder.jp/contests/abc248/tasks/abc248_b

fn calc(count: usize, a: usize, b: usize, k: usize) -> usize {
    if a >= b {
        count
    } else {
        calc(count+1, a*k, b, k)
    }
}

fn run(a: usize, b: usize, k: usize) -> usize {
    calc(0, a, b, k)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(2, run(1, 4, 2));
        assert_eq!(0, run(7, 7, 10));
        assert_eq!(6, run(31, 415926, 5));
        assert_eq!(1, run(158260522, 200224287, 10));
        assert_eq!(30, run(1, 1000000000, 2));
        assert_eq!(1, run(999999999, 1000000000, 500000000));
        assert_eq!(29, run(1, 536870912, 2));
    }
}

// https://atcoder.jp/contests/abc083/tasks/arc088_a

fn calc(n: usize, y: usize, count: usize) -> usize {
    if n > y {
        count
    } else {
        calc(n*2, y, count+1)
    }
}

fn run(x: usize, y: usize) -> usize {
    calc(x, y, 0)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(3, run(3, 20));
        assert_eq!(3, run(25, 100));
        assert_eq!(31, run(314159265, 358979323846264338));
    }
}

fn calc(num: usize, count: usize) -> usize {
    if num % 2 != 0 {
        count
    } else {
        calc(num/2, count+1)
    }
}

fn run(_n: usize, a: vec<usize>) -> usize {
    a.iter()
        .map(|num| {
            // 各要素が2で何回割り切れるかを合計
            calc(*num, 0)
        })
        .sum()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test() {
        assert_eq!(3, run2(3, vec![5, 2, 4]));
        assert_eq!(0, run2(4, vec![631, 577, 243, 199]));
        assert_eq!(39, run2(10, vec![2184, 2126, 1721, 1800, 1024, 2528, 3360, 1945, 1280, 1776]));
    }
}

// https://atcoder.jp/contests/abc029/tasks/abc029_c

fn func(n: usize, s: String, vec: &mut Vec<String>) -> Vec<String> {
    if n == 0 {
        vec.push(s);
        vec.clone()
    } else {
        for c in ["a", "b", "c"].iter() {
            func(n - 1, s.clone() + &c.to_string(), vec);
        }
        vec.clone()
    }
}

fn run(n: usize) -> Vec<String> {
    func(n, "".to_string(), &mut Vec::new())
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(usize, Vec<&'static str>);

    #[test]
    fn test() {
        let tests = [
            TestCase(1, vec!["a", "b", "c"]),
            TestCase(2, vec!["aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc"]),
        ];

        for TestCase(n, expected) in tests {
            assert_eq!(run(n), expected);
        }
    }
}

// すぐ書く

// https://atcoder.jp/contests/abc340/tasks/abc340_c

use std::collections::HashMap;

fn calc(n: usize, h: &mut HashMap<usize, usize>) -> usize {
    if n < 2 {
        return 0;
    }

    if let Some(x) = h.get(&n) {
        return *x;
    }

    let a = n/2;
    let b = if n % 2 == 0 { n / 2 } else { n / 2 + 1 };

    let num = n + calc(a, h) + calc(b, h);
    h.entry(n).or_insert(num);

    return num;
}

fn run(n: usize) -> usize {
    let mut hash_map: HashMap<usize, usize> = HashMap::new();

    calc(n, &mut hash_map)
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(usize, usize);

    #[test]
    fn test() {
        let tests = [
            TestCase(3, 5),
            TestCase(340, 2888),
            TestCase(100000000000000000, 5655884811924144128),
        ];

        for TestCase(n, expected) in tests {
            assert_eq!(run(n), expected);
        }
    }
}

// https://atcoder.jp/contests/atc001/tasks/dfs_a

fn check(h: isize, w: isize, i: isize, j: isize) -> bool {
    i < 0 || j < 0 || i >= h || j >= w
}

fn dfs(vec: &Vec<Vec<char>>, seen: &mut Vec<Vec<bool>>, cur_i: usize, cur_j: usize) {
    seen[cur_i][cur_j] = true;

    let dx = [0, 1, 0, -1];
    let dy = [1, 0, -1, 0];

    for i in 0..4 {
        if check(vec.len() as isize, vec[0].len() as isize, cur_i as isize + dx[i], cur_j as isize + dy[i]) {
            continue;
        }

        let next_i = (cur_i as isize + dx[i]) as usize;
        let next_j = (cur_j as isize + dy[i]) as usize;

        if vec[next_i][next_j] == '#' || seen[next_i][next_j] {
            continue;
        }

        dfs(&vec, seen, next_i, next_j)
    }
}

fn run(h: usize, w: usize, c: Vec<&str>) -> &'static str {
    let vec: Vec<Vec<char>> = c.into_iter().map(|str| str.chars().collect()).collect();

    let mut start = (0, 0);
    let mut end = (0, 0);

    for i in 0..h {
        for j in 0..w {
            if vec[i][j] == 's' {
                start = (i, j);
            }
            if vec[i][j] == 'g' {
                end = (i, j);
            }
        }
    }

    let mut seen = vec![vec![false; w]; h];

    dfs(&vec, &mut seen, start.0, start.1);

    if seen[end.0][end.1] {
        "Yes"
    } else {
        "No"
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(usize, usize, Vec<&'static str>, &'static str);

    #[test]
    fn test() {
        let tests = [
            TestCase(4, 5, vec!["s####", "....#", "#####", "#...g"], "No"),
            TestCase(4, 4, vec!["...s", "....", "....", ".g.."], "Yes"),
        ];

        for TestCase(h, w, c, expected) in tests {
            assert_eq!(run(h, w, c), expected);
        }
    }
}

// https://atcoder.jp/contests/abc277/tasks/abc277_c

use std::collections::{HashMap, HashSet};

fn dfs(current: usize, seen: &mut HashSet<usize>, graph: &HashMap<usize, Vec<usize>>) -> usize {
    let mut ans = current;
    seen.insert(ans);

    for tmp in graph.get(&current).unwrap() {
        if seen.contains(tmp) {
            continue;
        }

        ans = ans.max(dfs(*tmp, seen, graph));
    }

    ans
}

fn run(_n: usize, ab: Vec<(usize, usize)>) -> usize {
    let mut hash_map: HashMap<usize, Vec<usize>> = HashMap::new();

    for &(a, b) in ab.iter() {
        hash_map.entry(a).or_insert_with(|| Vec::new()).push(b);
        hash_map.entry(b).or_insert_with(|| Vec::new()).push(a);
    }

    // 1階からどこにも行けなかったら1を返す
    let Some(_) = hash_map.get(&1) else {
        return 1;
    };

    dfs(1, &mut HashSet::new(), &hash_map)
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(usize, Vec<(usize, usize)>, usize);

    #[test]
    fn test() {
        let tests = [
            TestCase(4, vec![(1, 4), (4, 3), (4, 10), (8, 3), (1, 2)], 10),
            TestCase(6, vec![(1, 3), (1, 5), (1, 12), (3, 5), (3, 12), (5, 12)], 12),
            TestCase(3, vec![(500000000, 600000000), (600000000, 700000000), (700000000, 800000000)], 1),
        ];

        for TestCase(n, ab, expected) in tests {
            assert_eq!(run(n, ab), expected);
        }
    }
}

// https://atcoder.jp/contests/abc396/tasks/abc396_d

use std::collections::HashMap;

fn dfs(
    n: usize,
    hash_map: &HashMap<usize, Vec<(usize, usize)>>,
    seen: &mut Vec<bool>,
    cur: usize,
    xor: usize,
    ans: &mut usize
) {
    seen[cur] = true;

    let Some(next) = hash_map.get(&cur) else {
        return;
    };

    for (w, next) in next {
        if *next == n {
            *ans = (*ans).min(w ^ xor);
            continue;
        }

        if seen[*next] {
            continue;
        }

        dfs(n, hash_map, seen, *next, w ^ xor, ans)
    }

    seen[cur] = false;
}

fn run(n: usize, _m: usize, uvw: Vec<(usize, usize, usize)>) -> usize {
    let mut hash_map = HashMap::new();

    for (u, v, w) in uvw {
        hash_map.entry(u).or_insert_with(|| Vec::new()).push((w, v));
        hash_map.entry(v).or_insert_with(|| Vec::new()).push((w, u));
    }

    let mut seen = vec![false; n+1];

    let mut ans = std::usize::MAX;

    dfs(n, &hash_map, &mut seen, 1, 0, &mut ans);

    ans
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(usize, usize, Vec<(usize, usize, usize)>, usize);

    #[test]
    fn test() {
        let tests = [
            TestCase(4, 4, vec![(1, 2, 3), (2, 4, 5), (1, 3, 4), (3, 4, 7)], 3),
            TestCase(4, 3, vec![(1, 2, 1), (2, 3, 2), (3, 4, 4)], 7),
            TestCase(7, 10, vec![(1, 2, 726259430069220777), (1, 4, 988687862609183408), (1, 5, 298079271598409137), (1, 6, 920499328385871537), (1, 7, 763940148194103497), (2, 4, 382710956291350101), (3, 4, 770341659133285654), (3, 5, 422036395078103425), (3, 6, 472678770470637382), (5, 7, 938201660808593198)], 186751192333709144),
        ];

        for TestCase(n, m, uvw, expected) in tests {
            assert_eq!(run(n, m, uvw), expected);
        }
    }
}

// https://atcoder.jp/contests/atc002/tasks/abc007_3

use std::collections::VecDeque;

fn run(r: usize, c: usize, s: (usize, usize), g: (usize, usize), v: Vec<&str>) -> usize {
    let vec: Vec<Vec<char>> = v.into_iter().map(|c| c.chars().collect()).collect();

    let mut graph = vec![vec![-1; c]; r];
    let mut queue = VecDeque::new();

    graph[s.0-1][s.1-1] = 0;
    queue.push_back((s.0-1, s.1-1));

    let dx = [0, -1, 0, 1];
    let dy = [-1, 0, 1, 0];

    while queue.len() > 0 {
        let cur = queue.pop_front().unwrap();

        for i in 0..4 {
            let h = (cur.0 as isize + dx[i]) as usize;
            let w = (cur.1 as isize + dy[i]) as usize;

            if vec[h][w] == '#' || graph[h][w] != -1 {
                continue;
            }

            graph[h][w] = graph[cur.0][cur.1] + 1;

            queue.push_back((h, w));
        }
    }

    graph[g.0-1][g.1-1] as usize
}

#[cfg(test)]
mod tests {
    use super::*;

    struct TestCase(usize, usize, (usize, usize), (usize, usize), Vec<&'static str>, usize);

    #[test]
    fn test() {
        let tests = [
            TestCase(7, 8, (2, 2), (4, 5), vec!["########", "#......#", "#.######", "#..#...#", "#..##..#", "##.....#", "########"], 11),
            TestCase(5, 8, (2, 2), (2, 4), vec!["########", "#.#....#", "#.###..#", "#......#", "########"], 10),
        ];

        for TestCase(r, c, s, g, v, expected) in tests {
            assert_eq!(run(r, c, s, g, v), expected);
        }
    }
}