Prüfen, ob ein Graph ein Stern-Graph ist
Gegeben ist ein ungerichteter Graph mit
v Knoten und e Kanten. Ihre Aufgabe besteht darin zu ermitteln, ob dieser Graph ein Stern-Graph ist. Ein Stern-Graph ist durch einen zentralen Knoten gekennzeichnet, der mit allen anderen Knoten verbunden ist. Die übrigen Knoten sind ausschließlich mit diesem zentralen Knoten verbunden und nicht miteinander.
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
v (1 ≤ v ≤ 100 000) und e (1 ≤ e ≤ 100 000).Die folgenden
e Zeilen enthalten jeweils ein Paar von ganzen Zahlen v1, v2 (1 ≤ v1, v2 ≤ v). Dies bedeutet, dass der Knoten v1 mit dem Knoten v2 verbunden ist und umgekehrt.Ausgabe
Das Programm soll
Yes ausgeben, wenn der Graph ein Stern-Graph ist, und No andernfalls.Beispiele
Eingabe | Ausgabe |
7 6
1 5
2 5
3 5
7 5
6 5
4 5 | Yes |
7 6
1 5
2 5
3 5
7 5
6 1
4 5 | No |
1 0 | Yes |
2 1
1 2 | Yes |
2 0 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB