Überprüfen, ob der Graph effizient ist
Gegeben ist ein ungerichteter Graph mit
v Knoten und e Kanten. Ihre Aufgabe besteht darin, zu untersuchen, ob dieser Graph effizient ist. Ein Graph gilt als effizient, wenn es möglich ist, von jedem Knoten zu jedem anderen Knoten in höchstens 2 Kanten zu gelangen.Eingabe
Die erste Zeile der Eingabe enthält zwei Ganzzahlen
v (1 ≤ v ≤ 100) und e (1 ≤ e ≤ 10 000).Die folgenden
e Zeilen enthalten jeweils zwei Ganzzahlen v1, v2 (1 ≤ v1, v2 ≤ v), die eine Kante zwischen v1 und v2 repräsentieren.Ausgabe
Das Programm soll
Yes ausgeben, falls der Graph effizient ist, andernfalls No.Beispiele
Eingabe | Ausgabe |
4 3
1 2
2 3
3 1 | No |
4 4
1 2
2 3
3 1
1 4 | Yes |
Erläuterung
- Knoten 4 ist nicht mit den anderen Knoten verbunden ⇒ Es ist nicht möglich, von Knoten 4 zu einem anderen in höchstens 2 Kanten zu gelangen.
- Es ist möglich, von jedem Knoten zu jedem anderen Knoten in höchstens 2 Kanten zu gelangen.
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB