Coloração de Grafos
Temos um grafo com
v vértices e e arestas, além de c cores disponíveis. O objetivo é verificar se é possível colorir esse grafo usando as c cores, de forma que nenhum par de nós adjacentes apresente a mesma cor.Entrada
A primeira linha contém três inteiros
v (1 ≤ v ≤ 20), e (0 ≤ e ≤ ) e c (1 ≤ c ≤ 10), que representam, respetivamente, o número de vértices, o número de arestas e o número de cores disponíveis.As próximas
e linhas descrevem as arestas do grafo. Em cada linha, encontram-se dois inteiros a e b (1 ≤ a, b ≤ n, a ≠ b), indicando uma aresta entre os vértices a e b.Saída
Imprima
YES se for possível colorir o grafo usando as c cores de forma que dois nós adjacentes nunca tenham a mesma cor. Caso não seja possível, imprima NO.Exemplos
Entrada | Saída |
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