<p>You are given a positive integer <code>n</code> representing the number of nodes in an <strong>undirected</strong> graph. The nodes are labeled from <code>1</code> to <code>n</code>.</p>

<p>You are also given a 2D integer array <code>edges</code>, where <code>edges[i] = [a<sub>i, </sub>b<sub>i</sub>]</code> indicates that there is a <strong>bidirectional</strong> edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code>. <strong>Notice</strong> that the given graph may be disconnected.</p>

<p>Divide the nodes of the graph into <code>m</code> groups (<strong>1-indexed</strong>) such that:</p>

<ul>
	<li>Each node in the graph belongs to exactly one group.</li>
	<li>For every pair of nodes in the graph that are connected by an edge <code>[a<sub>i, </sub>b<sub>i</sub>]</code>, if <code>a<sub>i</sub></code> belongs to the group with index <code>x</code>, and <code>b<sub>i</sub></code> belongs to the group with index <code>y</code>, then <code>|y - x| = 1</code>.</li>
</ul>

<p>Return <em>the maximum number of groups (i.e., maximum </em><code>m</code><em>) into which you can divide the nodes</em>. Return <code>-1</code> <em>if it is impossible to group the nodes with the given conditions</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/10/13/example1.png" style="width: 352px; height: 201px;" />
<pre>
<strong>Input:</strong> n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> As shown in the image we:
- Add node 5 to the first group.
- Add node 1 to the second group.
- Add nodes 2 and 4 to the third group.
- Add nodes 3 and 6 to the fourth group.
We can see that every edge is satisfied.
It can be shown that that if we create a fifth group and move any node from the third or fourth group to it, at least on of the edges will not be satisfied.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[1,2],[2,3],[3,1]]
<strong>Output:</strong> -1
<strong>Explanation:</strong> If we add node 1 to the first group, node 2 to the second group, and node 3 to the third group to satisfy the first two edges, we can see that the third edge will not be satisfied.
It can be shown that no grouping is possible.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 500</code></li>
	<li><code>1 &lt;= edges.length &lt;= 10<sup>4</sup></code></li>
	<li><code>edges[i].length == 2</code></li>
	<li><code>1 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= n</code></li>
	<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>
	<li>There is at most one edge between any pair of vertices.</li>
</ul>

from collections import deque, defaultdict

class Solution:
    def magnificentSets(self, n: int, edges: list[list[int]]) -> int:
        # Graph construction as an adjacency list
        G = {i: [] for i in range(1, n + 1)}
        for u, v in edges:
            G[u].append(v)
            G[v].append(u)

        # Function to check if the graph is bipartite and collect its connected component
        def bipartite(v):
            queue = deque([(v, 1)])  # (node, expected color)
            colors = defaultdict(int)  # All nodes initialized to 0 (uncolored)
            colors[v] = 1  # Start by coloring the first node with 1
            
            component = set()  # To track all nodes in this connected component
            
            while queue:
                i, exp = queue.popleft()  # Pop the node and its expected color
                component.add(i)  # Add node to current component
                
                for c in G[i]:  # For each neighbor of node i
                    if colors[c] == 0:  # If the neighbor is not colored
                        colors[c] = -exp  # Assign the opposite color
                        queue.append((c, -exp))  # Append neighbor with opposite expected color
                    elif colors[c] != -exp:  # If the neighbor is already colored and the color conflicts
                        return False, None  # Graph is not bipartite
            return True, component

        # Helper function to perform BFS and find the maximum depth of the graph component
        def bfs(v):
            queue = deque([v])
            visited = {v}
            depth = 0
            while queue:
                depth += 1  # This represents the depth (number of layers) of the BFS
                nxt = deque()
                for node in queue:
                    for neighbor in G[node]:
                        if neighbor not in visited:
                            visited.add(neighbor)
                            nxt.append(neighbor)
                queue = nxt
            return depth

        seen = set()  # To track visited nodes across components
        total_layers = 0
        
        # Check all nodes for components and bipartite conditions
        for i in range(1, n + 1):
            if i not in seen:  # Process each unvisited node
                is_bipartite, component = bipartite(i)
                if not is_bipartite:
                    return -1  # If the graph is not bipartite, return -1
                
                # Add the current component to seen set
                seen.update(component)
                
                # Perform BFS on all nodes in the component to find the maximum layers
                max_layers = 0
                for node in component:
                    max_layers = max(max_layers, bfs(node))
                
                # Add the maximum depth of this component to the result
                total_layers += max_layers
        
        return total_layers

19700