Verifica se il Grafo è Efficiente
Dato un grafo non orientato con
v vertici e e archi, devi controllare se è efficiente. Un grafo si dice efficiente se è possibile spostarsi da un nodo qualunque a un altro nodo qualsiasi percorrendo al massimo 2 archi.Input
La prima riga di input contiene due interi
v (1 ≤ v ≤ 100) ed e (1 ≤ e ≤ 10 000).Le successive
e righe includono coppie di interi v1 e v2 (1 ≤ v1, v2 ≤ v) che rappresentano un arco tra v1 e v2.Output
Il programma deve stampare
Yes se il grafo è efficiente e No in caso contrario.Esempi
Ingresso | Uscita |
4 3
1 2
2 3
3 1 | No |
4 4
1 2
2 3
3 1
1 4 | Yes |
Spiegazione
- Il vertice 4 non è collegato agli altri ⇒ non è possibile raggiungere gli altri vertici da 4 percorrendo al massimo 2 archi.
- In questo caso, invece, è possibile raggiungere qualunque vertice da qualunque altro vertice percorrendo al massimo 2 archi.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB