Verificare se il Grafo è una Corona
Dato un grafo non orientato con
v vertici e e spigoli, si richiede di verificare se si tratta di un grafo corona. Una corona è composta da una base e può avere un numero qualsiasi di “spine”. La base della corona consiste in un unico spigolo che collega due nodi ed è condiviso da tutte le spine. Ogni spina possiede un solo nodo connesso a entrambi i nodi della base.
Input
La prima riga dell’input contiene due interi
v (1 ≤ v ≤ 1000) ed e (1 ≤ e ≤ 10 000).Le
e righe successive contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v) che rappresentano uno spigolo tra v1 e v2.Output
Il programma deve stampare
Yes se il grafo corrisponde a una corona, altrimenti deve stampare No.Esempi
Input | Output |
4 4
1 2
2 3
3 1
1 4 | No |
7 11
3 4
2 3
2 4
1 3
1 4
7 3
7 4
6 3
6 4
5 3
5 4 | Yes |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB