Loading...
Loading...
Loading...
It is sports day, and the PT teacher wants to split n students, numbered 1 to n, into two teams. Every student must be on exactly one team. A team can be of any size, even empty.
The teacher has a list of m pairs of students who quarrelled this week. The two students of each pair must be on different teams. Students who are not in any pair can go on either team.
Print YES if such a split exists, otherwise print NO.
YES or NO.Example 1
Input
4 4 1 2 2 3 3 4 4 1
Output
YES
Students 1 and 3 form one team, 2 and 4 the other.
Example 2
Input
3 3 1 2 2 3 3 1
Output
NO
Students 1 and 2 must differ, and 3 must differ from both. With two teams that is impossible.
Try the problem first. Open one hint at a time.
Put any student on team A. Then everyone who quarrelled with them must be on team B, and everyone who quarrelled with those must be on team A.
So once one student of a group is placed, the teams of the whole group are forced. Spread the team numbers with a queue.
If you meet a quarrel pair where both students already have the same team, the split is impossible.
The quarrel pairs may form several separate groups. Start a new search from every student who has no team yet.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor