Algorithms and Data Structures

Check if a Graph is Balanced

A directed graph is balanced if the number of incoming and outgoing edges is the same for all the vertices. Given a graph with v vertices and e edges, you are asked to check if it’s balanced.

Input

The first line of the input contains two integers v (1 ≤ v ≤ 100 000) and e (1 ≤ e ≤ 100 000).
The following e lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.

Output

The program should print Yes if the graph is balanced and No otherwise.

Examples

Input
Output
3 2 1 2 2 3
No
3 3 1 2 2 3 3 1
Yes

Explanation

Example 1: Vertex 1 has no incoming edges, while has 1 outgoing edge ⇒ the graph is not balanced.
Example 1: Vertex 1 has no incoming edges, while has 1 outgoing edge ⇒ the graph is not balanced.
Example 2: All the vertices have 1 incoming and 1 outgoing edge ⇒ the graph is balanced.
Example 2: All the vertices have 1 incoming and 1 outgoing edge ⇒ the graph is balanced.
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue