Given an undirected graph, divide the nodes into the maximum number of groups so that every edge connects nodes in adjacent groups only. Return -1 if it is impossible. Pattern focus: Bipartite check. The graph must be bipartite, and the number of groups depends on the longest shortest-path layering within each component.
n = number of nodes, edges = undirected edge list
maximum number of groups or -1
Example 1:
Input:
n = 6 edges = [[1,2],[1,4],[2,3],[2,4],[3,5],[4,5]]
Output:
-1
Explanation:
A valid layering can create 4 groups in the largest component.
Example 2:
Input:
n = 3 edges = [[1,2],[2,3],[3,1]]
Output:
-1
Explanation:
An odd cycle makes the graph non-bipartite.
Example 3:
Input:
n = 4 edges = [[1,2],[3,4]]
Output:
4
Explanation:
Each component contributes a layering of length 2.