Graphenfärbung

Gegeben ist ein Graph mit v Knoten und e Kanten sowie c verfügbaren Farben. Es soll überprüft werden, ob man den Graphen mit den gegebenen c Farben so färben kann, dass keine benachbarten Knoten dieselbe Farbe besitzen.

Eingabe

Die erste Zeile enthält drei ganze Zahlen v (1 ≤ v ≤ 20), e (0 ≤ e ≤ ) und c (1 ≤ c ≤ 10). Sie geben die Anzahl der Knoten, die Anzahl der Kanten und die verfügbaren Farben an.

Die folgenden e Zeilen beschreiben die Kanten des Graphen. Jede dieser Zeilen enthält zwei ganze Zahlen a und b (1 ≤ a, b ≤ n, a ≠ b), die eine Kante zwischen den Knoten a und b angeben.

Ausgabe

Gib YES aus, wenn sich der Graph mit den vorhandenen c Farben so einfärben lässt, dass keine benachbarten Knoten dieselbe Farbe haben. Andernfalls gib NO aus.

Beispiele