Algorithms and Data Structures

Does the Graph Consist of Cliques?

A clique is a subset of vertices in an undirected graph such that every pair of distinct vertices in the clique is connected by an edge. In other words, a clique is a complete subgraph where all the vertices are adjacent to each other.
You are given an undirected graph with v vertices and e edges. We would like to know if the given graph is a collection of disjoint cliques.

Input

The first line of the input contains two integers v (1 ≤ v ≤ 1000) and e (1 ≤ e ≤ ).
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 given graph is a set of disjoint cliques and No otherwise.

Examples

Input
Output
3 3 1 2 2 3 1 3
Yes
5 4 1 2 2 3 1 3 4 5
Yes
5 5 1 2 2 3 1 3 3 4 4 5
No
 

Constraints

Time limit: 1 seconds

Memory limit: 512 MB

Output limit: 1 MB

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