Possible Bipartition

Given n people labeled from 1 to n and an array dislikes where dislikes[i] = [a, b] indicates that persons a and b dislike each other, return true if it is possible to split everyone into two groups such that no two people in the same group dislike each other. Otherwise, return false.

Examples

Example 1

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]

Output: true

Explanation: We can split them into two groups: {1, 4} and {2, 3}. No two people in the same group dislike each other.

Example 2

Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]

Output: false

Explanation: No matter how we split 3 people into two groups, at least two people who dislike each other end up in the same group.

Example 3

Input: n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]

Output: false

Explanation: The dislike relationships form an odd cycle of length 5, making a valid 2-partition impossible.

Constraints

• 1 <= n <= 2000
• 0 <= dislikes.length <= 10^4
• dislikes[i].length == 2
• 1 <= dislikes[i][0] < dislikes[i][1] <= n
• All pairs in dislikes are unique.