Besteht der Graph aus Cliquen?
Eine Clique ist eine Teilmenge von Knoten in einem ungerichteten Graphen, in der jedes Paar unterschiedlicher Knoten durch eine Kante verbunden ist. Mit anderen Worten ist eine Clique ein vollständiger Teilgraph, bei dem alle Knoten benachbart sind.
Wir haben einen ungerichteten Graphen mit
v Knoten und e Kanten gegeben. Unsere Frage ist, ob dieser Graph aus disjunkten Cliquen besteht.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
v (1 ≤ v ≤ 1000) und e (1 ≤ e ≤ ).Die darauffolgenden
e Zeilen enthalten jeweils zwei ganze Zahlen v1, v2 (1 ≤ v1, v2 ≤ v). Damit wird angegeben, dass der Knoten v1 mit dem Knoten v2 verbunden ist und umgekehrt.Ausgabe
Das Programm soll
Yes ausgeben, wenn der angegebene Graph eine Menge disjunkter Cliquen bildet, und No ansonsten.Examples
Input | Output |
3 3
1 2
2 3
1 3 | Yes |
5 4
1 2
2 3
1 3
4 5 | Yes |
5 5
1 2
2 3
1 3
3 4
4 5 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB