For a college quiz, n students must be split into two teams. Some pairs of students are rivals and must not be on the same team. Print YES if such a split exists and NO otherwise. Students with no rivals can go on either team.
Constraints
- 1 ≤ n ≤ 100000
- 0 ≤ m ≤ 200000
Input and output
- Input
- Line 1: n and m. Next m lines: a b (a rival pair).
- Output
- `YES` or `NO`.
Examples
Input 1
4 4
1 2
2 3
3 4
4 1Output
YESPut 1 and 3 in one team and 2 and 4 in the other.
Input 2
3 3
1 2
2 3
1 3Output
NOA triangle: whichever teams you pick, two rivals end up together.
Show hints
- Colour a student, then give every rival the opposite colour.
- The graph may have several separate groups; start a new colouring from each uncoloured student.
Show the explanation
The question asks whether the rivalry graph is bipartite. Run BFS from every uncoloured student: colour it 0, and give each neighbour the opposite colour of the current student. If you ever find a neighbour that already has the same colour, there is an odd cycle and no split exists. Restarting from each uncoloured student covers disconnected groups.
Original UniCircle question. Last reviewed 22 Oct 2026.