Split Into Two Teams

A coach has n players, numbered 0 to n - 1, and a list rivals of pairs [a, b] of players who refuse to play on the same team. Write can_split(n, rivals) that returns True if the players can be split into two teams so that no two rivals end up together, and False otherwise.

Every player must join one of the two teams. Players with no rivals can join either team, and a team may be empty.

Examples

can_split(4, [[0, 1], [1, 2], [2, 3]])  # returns True
can_split(3, [[0, 1], [1, 2], [2, 0]])  # returns False
can_split(5, [[0, 1], [2, 3]])  # returns True

In the second example players 0 and 1 must be on different teams, and player 2 is a rival of both, so wherever player 2 goes, a rival is already there.

Constraints

• 1 <= n <= 2000, with up to 5,000 pairs.
• The two players in a pair are different, and a pair may be repeated.
• The rivalries can form several separate groups of players.