Parade

Time limit2sMemory limit128 MB

Summary

Given an undirected graph with V vertices and E edges, decide whether it has an Eulerian circuit that traverses every edge exactly once.

Level: Medium6 of 10
Topics: Graph, Union-find, DFS, Implementation
Solved: No attempts yet

Problem

Jongwoo, representing the class of 2018, has been chosen as a member of the route selection committee for the parade celebrating Chung-Ang University's 100th anniversary. The parade route consists of certain points and connecting segments that join two points. Jongwoo wants to pass through every point and every connecting segment.

However, if the same connecting segment is traversed more than once, the residents of that segment will file complaints. The same point may be passed through more than once.

Write a program for Jongwoo, who wants to design a parade that passes through every segment without receiving complaints.

Input

The first line gives the number of points V and the number of connecting segments E. (1 ≤ V ≤ E ≤ 3000) The following E lines each give the numbers Va, Vb of the two points that the connecting segment joins, separated by a space. (1 ≤ Va, Vb ≤ V, Va ≠ Vb)

There are no two distinct connecting segments (Va1, Vb1) and (Va2, Vb2) with Va1 = Va2 and Vb1 = Vb2, and every point is guaranteed to have at least one connecting segment attached to it.

Output

Print YES if Jongwoo can build the route he wants, and NO otherwise.

Examples2

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