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

struct KitchenContext {
    recipe_index: HashMap<String, usize>, // Maps recipe names to their index in the ingredients list
    ingredients: Vec<Vec<String>>, // Stores ingredients required for each recipe
}

struct PreparationCache {
    can_prepare_cache: HashMap<String, bool>, // Caches whether a recipe/ingredient can be prepared
}

impl Solution {
    pub fn find_all_recipes(recipes: Vec<String>, ingredients: Vec<Vec<String>>, supplies: Vec<String>) -> Vec<String> {
        let kc = KitchenContext::new(&recipes, ingredients);
        let mut cache = PreparationCache::new(supplies);

        recipes.into_iter()
            .filter(|recipe| kc.can_prepare(recipe, &mut cache))
            .collect()
    }
}

impl KitchenContext {
    // Initializes the KitchenContext with given recipes and ingredients
    fn new(recipes: &[String], ingredients: Vec<Vec<String>>) -> Self {
        let mut recipe_index = HashMap::new();

        // Map each recipe to its corresponding index
        for (idx, recipe) in recipes.iter().enumerate() {
            recipe_index.insert(recipe.clone(), idx);
        }

        Self {
            recipe_index,
            ingredients,
        }
    }

    // Determines whether a recipe can be prepared
    fn can_prepare(&self, recipe: &str, cache: &mut PreparationCache) -> bool {
        // Check cache and lazily determine recipe index
        let mut recipe_idx = None;
        let cached_result = *cache.can_prepare_cache.entry(recipe.to_string()).or_insert_with(|| {
            recipe_idx = self.recipe_index.get(recipe).copied();
            false // Default to false to prevent cycles
        });

        // If already cached, return the stored value
        if recipe_idx.is_none() {
            return cached_result;
        }

        // Check if all ingredients can be prepared
        let idx = recipe_idx.unwrap();
        for ingredient in &self.ingredients[idx] {
            if !self.can_prepare(ingredient, cache) {
                return false;
            }
        }

        // Mark as preparable and return true
        cache.can_prepare_cache.insert(recipe.to_string(), true);
        true
    }
}

impl PreparationCache {
    // Initializes the cache with the given supplies
    fn new(supplies: Vec<String>) -> Self {
        let mut can_prepare_cache = HashMap::new();
        for supply in supplies {
            can_prepare_cache.insert(supply, true);
        }
        Self { can_prepare_cache }
    }
}