Разбор добавил Дмитрий Молчанов

Решение задачи состоит в проверке графа на двудольность - обходом в глубину проверяем, есть ли в графе циклы нечетной длины. Если есть - выводим NO, иначе - YES.