Verificar se o Grafo é Eficiente
Dado um grafo não direcionado com
v vértices e e arestas, é preciso determinar se ele é eficiente. Considera-se que um grafo é eficiente se for possível viajar de qualquer nó para qualquer outro nó percorrendo, no máximo, 2 arestas.Entrada
A primeira linha da entrada contém dois números inteiros
v (1 ≤ v ≤ 100) e e (1 ≤ e ≤ 10 000).As próximas
e linhas incluem pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v) que representam uma aresta entre v1 e v2.Saída
O programa deve imprimir
Yes se o grafo for eficiente e No caso contrário.Exemplos
Entrada | Saída |
4 3
1 2
2 3
3 1 | No |
4 4
1 2
2 3
3 1
1 4 | Yes |
Explicação
- O vértice 4 não se conecta com os demais ⇒ não é possível viajar do vértice 4 até qualquer outro percorrendo, no máximo, 2 arestas.
- Consegue-se alcançar qualquer vértice a partir de qualquer outro vértice percorrendo, no máximo, 2 arestas.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB