Prüfen, ob der Graph eine Krone (Crown) ist
Gegeben ist ein ungerichteter Graph mit
v Knoten und e Kanten. Sie sollen überprüfen, ob er ein Kronengraph (crown graph) ist. Eine Krone (crown) besteht aus einer Basis und kann eine beliebige Anzahl von Spikes enthalten. Die Basis der Krone ist eine einzige Kante, die zwei Knoten miteinander verbindet, und diese Kante wird für alle Spikes gemeinsam genutzt. Jeder Spike hat genau einen Knoten, der sowohl mit dem einen als auch mit dem anderen Knoten der Basis verbunden ist.
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
v (1 ≤ v ≤ 1000) und e (1 ≤ e ≤ 10 000).In den folgenden
e Zeilen stehen jeweils zwei ganze Zahlen v1, v2 (1 ≤ v1, v2 ≤ v), die eine Kante zwischen v1 und v2 repräsentieren.Ausgabe
Das Programm soll
Yes ausgeben, wenn der Graph ein Kronengraph ist, und No, falls dies nicht der Fall ist.Beispiele
Eingabe | Ausgabe |
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