Раскраска графа
Вам дан граф с
v вершинами и e ребрами, а также c доступных цветов. Ваша задача — определить, можно ли раскрасить граф, используя эти c цветов таким образом, чтобы никакие смежные вершины не имели одинаковый цвет.Входные данные
Первая строка содержит три целых числа
v (1 ≤ v ≤ 20), e (0 ≤ e ≤ ) и c (1 ≤ c ≤ 10), которые соответствуют количеству вершин, количеству ребер и числу доступных цветов соответственно.В следующих
e строках перечислены ребра графа. Каждая строка содержит два целых числа a и b (1 ≤ a, b ≤ n, a ≠ b), обозначающих ребро между вершинами a и b.Выходные данные
Выведите
YES, если существует способ раскрасить граф, используя c цветов так, чтобы никакие смежные вершины не были окрашены в один и тот же цвет. Иначе выведите NO.Примеры
Входные данные | Выходные данные |
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