O grafo consiste em cliques?
Uma clique é um subconjunto de vértices em um grafo não dirigido em que todo par de vértices distintos do subconjunto está ligado por uma aresta. Em outras palavras, uma clique é um subgrafo completo onde todos os vértices estão adjacentes entre si.
É dado um grafo não dirigido com
v vértices e e arestas. Queremos saber se o grafo em questão é uma coleção de cliques disjuntas.Entrada
A primeira linha da entrada contém dois inteiros
v (1 ≤ v ≤ 1000) e e (1 ≤ e ≤ ).As próximas
e linhas contêm pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v) indicando que o vértice v1 está ligado ao vértice v2 e vice-versa.Saída
O programa deve imprimir
Yes se o grafo for um conjunto de cliques disjuntas e No caso contrário.Exemplos
Entrada | Saída |
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