Divide Nodes Into the Maximum Number of Groups
You are given a positive integer n representing the number of nodes in an undirected graph. The nodes are labeled from 1 to n.
You are also given a 2D integer array edges, where edges[i] = [ai, bi] indicates that there is a bidirectional edge between nodes ai and bi. Notice that the given graph may be disconnected.
Divide the nodes of the graph into m groups (1-indexed) such that:
- Each node in the graph belongs to exactly one group.
- For every pair of nodes in the graph that are connected by an edge
[ai, bi], ifaibelongs to the group with indexx, andbibelongs to the group with indexy, then|y - x| = 1.
Return the maximum number of groups (i.e., maximum m) into which you can divide the nodes. Return -1 if it is impossible to group the nodes with the given conditions.
Example 1
Input
n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]Output
4The nodes can be divided into four groups, for example with node 5 in group 1, node 1 in group 2, nodes 2 and 4 in group 3, and nodes 3 and 6 in group 4, and no valid division can create a fifth group.
Example 2
Input
n = 3, edges = [[1,2],[2,3],[3,1]]Output
-1The three nodes form a cycle of length three, so satisfying two edges forces the third edge to violate the required group-index difference.
Constraints
- 1 <= n <= 500
- 1 <= edges.length <= 10^4
- edges[i].length == 2
- 1 <= ai, bi <= n
- ai != bi
- There is at most one edge between any pair of vertices.