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
Eingabe | Ausgabe |
3 3 3
1 2
2 3
3 1 | YES |
3 3 2
1 2
2 3
3 1 | NO |
4 4 2
1 2
2 3
3 4
4 1 | YES |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB