Strange Game on a Graph

Time limit2sMemory limit1024 MB

Summary

Two players alternately erase edges, each new edge must share a vertex with the previous one. Determine whether the first player can force a win on a given graph.

Level: Medium7 of 10
Topics: Graph, Game theory, Math
Solved: No attempts yet

Statement

Arthur Fleck lives with his sick mother. To cheer her up, he suggested they play a fun board game.

First, Arthur asks his mother to draw an undirected graph on a sheet of paper with a pencil. The graph has no self-loops and no multiple edges. Then the two take turns making moves. On his first move, Arthur chooses an edge of this graph and erases it. On each following move, the current player may erase an edge that is adjacent to the edge erased on the previous move. Two edges are adjacent if they share a common vertex. The player who cannot make a move loses.

The figure shows a possible sequence of moves in this game. Dashed edges are the ones erased during the game. The numbers on the erased edges give the order in which they are erased.

Arthur does not want to hurt his mother's feelings, so he does not plan to let her win. Both players want to win and play optimally. Knowing the graph the game is played on, determine whether Arthur can win.

Input

The first line contains two integers $n$ and $m$ , the number of vertices and the number of edges in the graph ( $2 \le n \le 10^4$ , $1 \le m \le 10^4$ ).

Each of the next $m$ lines contains a pair of integers $a_i$ , $b_i$ , the vertices connected by the $i$ -th edge ( $1 \le a_i, b_i \le n$ ).

It is guaranteed that the graph has no self-loops and no multiple edges.

Output

Print YES on a single line if Arthur can win, and NO otherwise.

Examples2

Example 1
Input
```
7 5
1 2
5 1
5 6
3 2
2 4
```
Expected output
```
YES
```
Example 2
Input
```
3 2
1 2
2 3
```
Expected output
```
NO
```