Restaurants

Time limit1sMemory limit128 MB

Summary

Given a graph with up to 100000 nodes and edges, decide if edges can be 2-colored so every vertex of degree at least 2 sees both colors among its incident edges.

Level: Medium5 of 10
Topics: Graph, DFS, Greedy
Solved: No attempts yet

Problem

There is a country of N cities connected by E bidirectional highways. Two competing restaurant chains, chain 1 and chain 2, have agreed to split the market fairly. At the center of each highway exactly one restaurant, belonging to one of the two chains, may be built.

For fairness, every city that is connected to two or more highways must have, among the highways connected to it, at least one restaurant of chain 1 and at least one restaurant of chain 2. A city connected to only one highway, or to none, is excluded from this rule, because the two chains do not need to be adjacent there.

Write a program that decides whether it is possible to assign one of the two chains to every highway so that all of these conditions are satisfied.

Input

The first line contains the number of cities N and the number of highways E. (1 ≤ N, E ≤ 100000)

Each of the next E lines contains two integers Ai and Bi describing a highway that connects city Ai and city Bi. Ai and Bi are different, and no two highways connect the same pair of cities.

Output

Print YES on a single line if it is possible to assign a chain to every highway so that the conditions hold, and NO otherwise.

Examples4

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