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: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB