A game lobby has n players numbered 1 through n. Some pairs of players are declared rivals. You want to split every player into exactly one of two factions so that each declared rivalry is between a player in one faction and a player in the other (no rivalry sits inside a single faction). A player with no rivalries may go in either faction.
Decide whether such a split is possible.
Input format
Line 1: two integers n and m.
Next m lines: two integers u and v, a rivalry between players u and v. Each unordered rivalry is listed at most once and never joins a player to themselves.
Output format
Print YES if a valid two-faction split exists, otherwise print NO.
Constraints
- 1 <= n <= 100000
- 0 <= m <= 200000
- 1 <= u, v <= n and u != v