Coloration de Graphes
Vous disposez d’un graphe comportant
v sommets et e arêtes, ainsi que c couleurs disponibles. Votre tâche consiste à déterminer s’il est possible de colorier ce graphe en utilisant les c couleurs fournies de manière à ce qu’aucun sommet adjacent ne partage la même couleur.Entrée
La première ligne contient trois entiers
v (1 ≤ v ≤ 20), e (0 ≤ e ≤ ) et c (1 ≤ c ≤ 10). Ils indiquent respectivement le nombre de sommets, le nombre d’arêtes et le nombre de couleurs disponibles.Les
e lignes suivantes décrivent chacune une arête du graphe. Chaque ligne contient deux entiers a et b (1 ≤ a, b ≤ n, a ≠ b), qui indiquent qu’il y a une arête entre les sommets a et b.Sortie
Affichez
YES s’il est possible de colorier le graphe avec les c couleurs de telle sorte qu’aucun sommet adjacent n’ait la même couleur. Dans le cas contraire, affichez NO.Exemples
Entrée | Sortie |
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