Split into two teams

Problem

A coach has n players and m pairs of players who must not be on the same team. Decide whether everyone can be placed in one of two teams so that no pair is on the same team.

Input, output and limits

Input: Line 1: n and m. Then m lines, each with two players a and b who conflict. Players are numbered 0 to n - 1.
Output: YES if the split is possible, otherwise NO.
Constraints: 1 ≤ n ≤ 2000
0 ≤ m ≤ 5000
No node is linked to itself and no pair is listed twice

Examples

Example 1

Input

Output

YES

Example 2

Input

Output

NO

Hints

Try the problem first. Open one hint at a time.

Hint 1

Colour the first player of each group red and its conflicts blue, and keep alternating.

Hint 2

Meeting a neighbour that already has your own colour means NO.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Exactly k links awaymedium
Print the shortest routemedium
Largest land patchmedium
Spreading infectionhard
Shortest way through the mazemedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Graphs: Basics & Traversal problems

Problem

Input, output and limits

Examples

Hints

More Graphs: Basics & Traversal problems