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

impl Solution {
    pub fn magnificent_sets(n: i32, edges: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut graph = vec![vec![]; n];

        // Build adjacency list representation of the graph
        for edge in edges {
            let (u, v) = ((edge[0] - 1) as usize, (edge[1] - 1) as usize);
            graph[u].push(v);
            graph[v].push(u);
        }

        let mut heights = HashMap::new(); // Store the maximum height for each component

        // Iterate over all nodes, attempting to maximize height for each connected component
        for start in 0..n {
            if let Some((component_id, height)) = Self::bfs_check_and_find_height(start, &graph) {
                heights.entry(component_id)
                        .and_modify(|h| *h = height.max(*h))
                        .or_insert(height);
            } else {
                return -1; // If any component is not bipartite, return -1
            }
        }

        heights.values().sum()
    }

    // Performs BFS from `start` to determine if the graph is bipartite
    // and find the maximum height in its connected component.
    fn bfs_check_and_find_height(start: usize, graph: &[Vec<usize>]) -> Option<(usize, i32)> {
        let mut level = vec![0 as i32; graph.len()]; // Track BFS levels
        let mut queue = VecDeque::new();
        queue.push_back(start);
        level[start] = 1;

        let mut max_level = 1;   // Track the deepest BFS level reached
        let mut min_index = start;

        while let Some(v) = queue.pop_front() {
            max_level = level[v]; // Update the deepest level reached
            min_index = min_index.min(v);

            // Traverse neighbors and check bipartiteness
            for &u in &graph[v] {
                if level[u] == 0 { // First visit to `u`
                    level[u] = level[v] + 1;
                    queue.push_back(u);
                } else if level[u].abs_diff(level[v]) != 1 { // Bipartiteness check
                    return None // Graph is not bipartite
                }
            }
        }

        Some((min_index, max_level))
    }
}