Colorazione dei grafi
Vi viene fornito un grafo con
v vertici e e archi, insieme a c colori disponibili. Il vostro compito consiste nel verificare se sia possibile colorare il grafo utilizzando i c colori dati in modo tale che nessun vertice adiacente abbia lo stesso colore.Input
La prima riga contiene tre interi
v (1 ≤ v ≤ 20), e (0 ≤ e ≤ ) e c (1 ≤ c ≤ 10), che rappresentano rispettivamente il numero di vertici, il numero di archi e il numero di colori disponibili.Le successive
e righe descrivono gli archi del grafo. Ogni riga contiene due interi a e b (1 ≤ a, b ≤ n, a ≠ b) che indicano un arco tra i vertici a e b.Output
Stampate
YES se è possibile colorare il grafo con i c colori senza che esistano vertici adiacenti che abbiano lo stesso colore. In caso contrario, stampate NO.Esempi
Input | Output |
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