$1\mathrm{.}1$ Problem $1[15$ pts$]$

Problem $1.$ In the epic world of comics, There are two teams: Heroes and Villains. Each character may have

rivalries with others, leading to intense conflicts. Given a list of characters from both universes and pairs that

indicate rivalries, your task is to create an algorithm that determines if it's possible to assign each character to

either the Heroes or the Villains such that:

Every rivalry exists between a Hero and a Villain.

No two characters from the same group have a rivalry.

Requirements:

Design an efficient algorithm that decides whether such an assignment is possible.

If it is possible, your algorithm should produce the assignment of characters to their respective groups.

Analyze the time complexity of your solution.

Provide a brief explanation of your algorithm's logic. Discuss any potential edge cases and how your algorithm

addresses them.