use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    fn dfs(root: Option<&Rc<RefCell<TreeNode>>>, path: String, ans: &mut Vec<String>) {
        let map = vec!['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
        'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'];
        if let Some(n) = root {
            let mut val = map[RefCell::borrow(n).val as usize].to_string();
            val.push_str(&path);

            if RefCell::borrow(&n).left.is_none() && RefCell::borrow(&n).right.is_none() {
                ans.push(val.clone());
                return;
            }
            if !RefCell::borrow(&n).left.is_none() {
                Self::dfs(RefCell::borrow(&n).left.as_ref(), val.clone(), ans);
            }
            if !RefCell::borrow(&n).right.is_none() {
                Self::dfs(RefCell::borrow(&n).right.as_ref(), val.clone(), ans);
            }
        }
    }

    pub fn smallest_from_leaf(root: Option<Rc<RefCell<TreeNode>>>) -> String {
        let mut ans = vec![];
        Self::dfs(Some(&root.unwrap()), "".to_string(), &mut ans);
        ans.sort();
        
        return ans[0].clone();
    }
}

impl Solution {
    fn compute(a: &Vec<i32>, kk: i32) -> i32 {
        let mut count = vec![0; a.len() + 1];
        let (mut i, mut ans, mut k) = (0, 0, kk);
        for j in 0..a.len() {
            if count[a[j] as usize] == 0 {
                k -= 1;
            }
            count[a[j] as usize] += 1;

            while k < 0 {
                count[a[i] as usize] -= 1;
                i += 1;
                if count[a[i - 1] as usize] == 0 {
                    k += 1;
                }
            }

            ans += j - i  + 1;
        }
        return ans as i32;
    }
    pub fn subarrays_with_k_distinct(a: Vec<i32>, k: i32) -> i32 {
        return Self::compute(&a, k) - Self::compute(&a, k - 1);
    }
}

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

impl Solution {
    pub fn find_judge(n: i32, trust: Vec<Vec<i32>>) -> i32 {
        let mut map: HashMap<i32, HashSet<i32>> = HashMap::new();
        let mut ans = 1;
        for p in trust {
            let (k, v) = (p[0], p[1]);
            map.entry(k).or_insert(HashSet::new());
            map.get_mut(&k).unwrap().insert(v);
        }

        for i in 1..n + 1 {
            if ans == i {
                continue;
            }
            if map.contains_key(&ans) {
                ans = i;
            }
        }

        for i in 1..n + 1 {
            if ans == i {
                continue;
            }

            if map.contains_key(&ans) || map.get(&i).is_none() ||
                !map.get(&i).unwrap().contains(&ans) {
                return -1;
            }
        }

        return ans;
    }
}