use std::collections::HashMap;


use std::collections::HashSet;

impl Solution {
    pub fn shortest_way(source: String, target: String) -> i32 {
        let (ss, st, mut ans) = (source.len(), target.len(), 1);
        let mut set = HashSet::new();
        for c in source.chars() {
            set.insert(c);
        }
        let (mut i, mut j) = (0, 0);
        while i < st {
            if !set.contains(&target.chars().nth(i).unwrap()) {
                return -1;
            }
            while j < ss && source.chars().nth(j).unwrap()
                != target.chars().nth(i).unwrap() {
                j += 1;
            }
            if j == ss {
                j = 0; i -= 1; ans += 1;
            } else {
                j += 1;
            }
            i += 1;
        }

        return ans;
    }
} 

use std::collections::HashMap;

impl Solution {
    pub fn confusing_number(n: i32) -> bool {
        let s = n.to_string();

        let map: HashMap<char, char> = [('1', '1'), ('6', '9'), ('8', '8'), ('9', '6'), ('0','0')]
            .iter().cloned().collect();
        let (mut changed, mut i, mut j) = (false, 0, s.len() - 1);
        while i <= j {
            if !map.contains_key(&s.chars().nth(i).unwrap())
                || !map.contains_key(&s.chars().nth(j).unwrap()) {
                return false;
            }
            if map[&s.chars().nth(i).unwrap()] != s.chars().nth(j).unwrap() {
                changed = true;
            }
            i += 1;
            if j != 0 {
                j -= 1;
            }
        }

        return changed;
    }
}

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

impl Solution {
    fn dfs(g: &HashMap<i32, HashSet<i32>>, i: i32, des: i32, visited: &mut HashMap<i32, i32>) -> bool {
        if !g.contains_key(&i) || g.get(&i).unwrap().is_empty() {
            return i == des;
        }
        if visited.contains_key(&i) {
            let val = visited.get(&i).unwrap();
            if *val == 1 {
                return false;
            }
            if *val == -1 {
                return true;
            }
        } else {
            visited.insert(i, 1);
        }
        for neib in g.get(&i).unwrap() {
            if !Self::dfs(g, *neib, des, visited) {
                return false;
            }
        }
        visited.insert(i, -1);
        return true;
    }

    pub fn leads_to_destination(n: i32, edges: Vec<Vec<i32>>, source: i32, destination: i32) -> bool {
        let (mut g, mut visited) = (HashMap::new(), HashMap::new());
        for e in edges {
            if !g.contains_key(&e[0]) {
                g.insert(e[0], HashSet::new());
            }
            let mut val = g.get(&e[0]).unwrap().clone();
            val.insert(e[1]);
            g.insert(e[0], val);
        }
        return Self::dfs(&g, source, destination, &mut visited);
    }
}