<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>

class Solution:
    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
        # Find max number of groups the current connected component can be divided into by doing BFS starting from each node in the current connected component.
        def bfs_cc(start_node: int) -> int:
            '''BFS on connected components starting from start_node'''
            q = collections.deque([start_node])
            group_cnt = 0
            connected_visited = set([start_node])
            while (length := len(q)) > 0:
                while length > 0:
                    cur = q.popleft()
                    length -= 1
                    for adj in graph[cur]:
                        if adj not in connected_visited:
                            q.append(adj)
                            connected_visited.add(adj)
                group_cnt += 1
            return group_cnt
        # Build a graph.
        graph = collections.defaultdict(set)
        for a, b in edges:
            graph[a].add(b)
            graph[b].add(a)
        
        # Divide and conquer
        # 1. Divide the graph into connected components;
        # 2. Conquer each connected component to find the max number of groups it can be divided into by BFS;
        # 3. Combine the max number of groups each connected component can be divided into.
        ans = 0
        # visited stores all nodes that belong to connected components(CC's) that have been explored.
        # "Explored" means that a CC is chekced to be bipartite and we have calculated the max number of groups it cna be divided into.
        visited = set()
        for node in range(1, n + 1):
            if node not in visited:
                # Find a connected component by BFS and check whether it is bipartite on the go.
                # If it is bipartie, there is no cycle with odd number of edges,
                # meaning that it is possible to divide the current connected component into groups without violating the rules.
                connected = set()  # Stores nodes in the current component.
                color = [0] * (n + 1)  # There are two colors in a bipartite graph, 1 and -1.
                color[node] = 1
                q = deque([node])

                while q:
                    curr_node = q.popleft()
                    connected.add(curr_node)
                    for neigh in graph[curr_node]:
                        if color[neigh] != 0:
                            if color[neigh] != -color[curr_node]:
                                return -1
                        else:
                            color[neigh] = -color[curr_node]
                            q.append(neigh)
                
                max_group_cnt = 0
                for start_node in connected:
                    group_cnt = bfs_cc(start_node)
                    max_group_cnt = max(max_group_cnt, group_cnt)
                
                # Combine
                visited |= connected  # Merge nodes in the current connected component into the global visited nodes, all nodes in connected are explored.
                ans += max_group_cnt
        
        return ans


21200