An undirected graph contains n nodes labeled 1 through n. Each pair in edges connects two nodes. The graph may have multiple disconnected components.
Assign every node to exactly one nonempty group. Number the groups consecutively from 1. The endpoints of every edge must belong to groups whose numbers differ by exactly 1.
Return the largest possible number of groups. If no assignment satisfies every edge, return -1.
Example 1:
Input: n = 5
edges = [[1,2],[2,3],[3,4]]
Output: 5Explanation: Place nodes 1, 2, 3, and 4 in groups 1, 2, 3, and 4 respectively. Isolated node 5 can occupy group 5. Every edge joins consecutive groups, and five nodes cannot fill more than five nonempty groups.
Example 2:
Input: n = 4
edges = [[1,2],[2,3],[3,4],[4,1]]
Output: 3Explanation: Use groups [1], [2,4], and [3]. Every edge joins consecutive groups. Four groups would place every node separately, but the cycle would then contain an edge that skips a group. The maximum is 3.
Example 3:
Input: n = 4
edges = [[1,2],[2,3],[3,1]]
Output: -1Explanation: Nodes 1, 2, and 3 form a triangle. If node 2 is one group away from node 1, no group for node 3 can be one group away from both. Isolated node 4 does not remove this conflict, so the answer is -1.
Constraints:
1 <= n <= 5001 <= edges.length <= 10000- Each edge contains two distinct integer node labels between
1andn. - At most one edge connects any pair of nodes.
- The graph may be disconnected.