Подсказка к задаче 495

Предположите, что граф распадается на две компоненты и воспользуйтесь четностью.