<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:
    # solution: https://www.youtube.com/watch?v=MSG7qX_UiKQ
    def maxDistance(self, node: int, adj: List[List[int]], visited: List[int], distance: List[int]) -> int:
        if visited[node]:
            return distance[node]
        visited[node] = True
        # print(f"distance = {distance}")
        # print(f"node = {node}")
        maxGroupCount = distance[node]
        for neighbor in adj[node]:
            maxGroupCount = max(
                maxGroupCount, self.maxDistance(neighbor, adj, visited, distance)
                )
        return maxGroupCount

    def bfs(self, node: int, adj: List[List[int]], n: int):
        visited = [False] * (n + 1)
        q = deque([node])
        visited[node] = True
        distance = 0
        while q:
            size = len(q)
            for i in range(size):
                node = q.pop()
                for neighbor in adj[node]:
                    if not visited[neighbor]:
                        q.appendleft(neighbor)
                        visited[neighbor] = True
            distance += 1
        return distance

    def getMaxGroupCount(self, adj: List[List[int]], n: int) -> int:
        # find minimum distance to the farthest node in the graph for each node
        distance = [self.bfs(i, adj, n) for i in range(1, n + 1)]
        # to account for node numberings being 1 -> n
        distance.insert(0, 0)
        maxGroupCount = 0
        # go through each connected component in the graph via dfs
        # and find the node which has the maximum distance in each component
        # just sum up all the max distances across each component and return
        visited = [False] * (n + 1)
        # print(f"n = {n}")
        for node in range(1, n + 1):
            if not visited[node]:
                maxGroupCount += self.maxDistance(node, adj, visited, distance)
        return maxGroupCount

    def isValid(self, adj: List[List[int]], node: int, visited: List[int], flag: List[bool], color: int):
        # check if node is visited then the color marked for the node should be of what was set in visited
        # if otherwise => graph isn't bipartite
        if visited[node] != -1:
            flag[0] = flag[0] & (color == visited[node])
            return
        visited[node] = color
        for adjacent_vertex in adj[node]:
            if not flag[0]:
                return
            self.isValid(adj, adjacent_vertex, visited, flag, 1 - color)

    def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
        # create adjacency list from edges list to represent graph
        adj = [[] for _ in range(n + 1)]
        # undirected graph with bidirectional edges
        for s, d in edges:
            adj[s].append(d)
            adj[d].append(s)
        
        # flag to indicate if provided graph has cycles of odd length or not
        # if True - then no odd-length cycles
        # if False - then odd-length cycles => return -1 (as adjacent vertices of the graph cannot be put into separate groups)
        # adjacent vertices - edge exists between the 2 vertices
        flag = [True]
        visited = [-1] * (n + 1)
        for i in range(1, n + 1):
            if flag[0] and visited[i] == -1:
                self.isValid(adj, i, visited, flag, 1)
        
        if not flag[0]:
            return -1
        
        return self.getMaxGroupCount(adj, n)
        
20900