Раскраска графа в три цвета с доп условиями

Совершенно не представляю как подступиться к задаче. Понимаю лишь, что в случае наличия цикла нечетной длины состоящей из одного цвета(как во втором примере) перекраска невозможна. Прошу хотя бы дать идею. https://informatics.msk.ru/mod/statements/view.php?chapterid=413 - ссылка на проверяющую систему