ЛШКН-2017: 9. Обход в глубину и все такое

Дан невзвешенный граф, у которого вершины раскрашены в один из трех цветов. Необходимо перекрасить вершины графа таким образом, чтобы не было двух соседних вершин одного цвета, а также каждая вершина изменила цвет.