Coloración de Grafos
Se proporciona un grafo con
v vértices y e aristas, junto con c colores disponibles. Tu objetivo es determinar si es posible colorear el grafo usando esos c colores de manera que ningún nodo adyacente tenga el mismo color.Entrada
La primera línea contiene tres números enteros
v (1 ≤ v ≤ 20), e (0 ≤ e ≤ ) y c (1 ≤ c ≤ 10), que representan la cantidad de vértices, la cantidad de aristas y la cantidad de colores disponibles, respectivamente.Las siguientes
e líneas describen las aristas del grafo. Cada línea incluye dos números enteros a y b (1 ≤ a, b ≤ n, a ≠ b) que indican una arista entre los vértices a y b.Salida
Imprime
YES si es posible colorear el grafo usando los c colores de manera que ningún nodo adyacente comparta el mismo color. En caso contrario, imprime NO.Ejemplos
Entrada | Salida |
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