Cперва можно придумать простое, но медленное решение: пока мы не получили ответ, возьмем две вершины четной степени из одной компоненты, найдем путь между ними и поменяем состояния ребер на нем. Количество вершин четной степени уменьшится на два, и ответ найдется всегда, если он есть. Так как, если осталась ровно одна вершина четной степени, то по соображениям четности суммарного числа степеней вершин ответ не достижим.

После этого, наверное, можно придумать совершенно не связанное с предыдущим решение — обычную жадность. Пускаем дфс, который возвращает bool, означающий нужно ли брать в ответ ребро, по которому был сделан переход. Почему это работает? По соображениям предыщуего решения — если в каком-то поддереве дфса все вершины уже имеют нечетную степень, то возможно иправить все остальные вершины не трогая это поддерево. То есть, жадность работает =)

Вот мы находимся в какой-то компоненте связности. В какой-то момент времени некоторое ребро удалится и компонента распадётся на две. Построим дерево на этих компонентах, для каждой вершины которого сохраним время, когда эта компонента образовалась, и размер компоненты. Листьями в этом дереве будут компоненты соответсвующие вершинкам в исходном графе.

Поиском в ширину найдём листья, до которых можно дойти, и выберем тот лист, где сумма на пути до корня (для каждой вершинки произведение размера компоненты на время существования этой компоненты) максимальна.

Код тут.