Group Division Feasibility

MEDIUM30 pts

You are organizing an event with n participants, labeled from 1 to n. Due to personal differences, some participants have conflicts with each other—if two participants are in conflict, they absolutely cannot be placed in the same team.

Your task is to determine whether it is possible to divide all n participants into exactly two teams (of any size) such that no two conflicting participants end up on the same team.

You are given an integer n representing the total number of participants, and a 2D integer array conflicts where each element conflicts[i] = [personA, personB] indicates that participant personA and participant personB have a conflict and must be placed in different teams.

Return true if such a division into two teams is possible, or false otherwise.

Key Observations:

Each participant must be assigned to exactly one of the two teams.
Both teams can be of any size (including the possibility of one team being empty, though typically constraints ensure both teams have members).
The conflict relationship is symmetric: if person A conflicts with person B, then person B also conflicts with person A.
Participants with no listed conflicts can be placed in either team.

Example

Input

n = 4
conflicts = [[1,2],[1,3],[2,4]]

Output

true

Explanation

We can divide the participants into two teams: Team 1 = {1, 4} and Team 2 = {2, 3}. Participant 1 conflicts with 2 and 3, but they are in different teams. Participant 2 conflicts with 4, and they are also in different teams. All conflict constraints are satisfied.

Example

Input

n = 3
conflicts = [[1,2],[1,3],[2,3]]

Output

false

Explanation

Participant 1 conflicts with both 2 and 3, so 2 and 3 must be on the same team. However, 2 and 3 also conflict with each other, so they cannot be on the same team. This creates an impossible situation—there is no valid way to divide these three participants into two teams.

Example

Input

n = 5
conflicts = [[1,2],[3,4],[4,5]]

Output

true

Explanation

One valid division is: Team 1 = {1, 3, 5} and Team 2 = {2, 4}. Verify: 1-2 conflict (different teams ✓), 3-4 conflict (different teams ✓), 4-5 conflict (different teams ✓). All constraints are satisfied.

Accepted0/0·0% Acceptance

Constraints

1 ≤ n ≤ 2000
0 ≤ conflicts.length ≤ 10⁴
conflicts[i].length == 2
1 ≤ personA < personB ≤ n
All conflict pairs are unique (no duplicates).

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

n =

dislikes =

[[1,2],[1,3],[2,4]]

Group Division Feasibility

Hints

Group Division Feasibility

Hints