Розбір

Перефразуємо задачу. Нам дано список ребер, треба розбити на відрізки цей список, щоб враховуючи ребра з кожного відрізку окремо виходив двудольний граф.

Давайте будемо йти й жадібно добирати ребра в граф, поки це ребро нічого не псує. Як ми можемо швидко перевірити, чи псує нам ребро двудольність? Скористаємось СНМ. Будемо в кожній вершинці підтримувати предка і парність довжини шляху до кореня. Таким чином ми "пофарбували" всі вершинки у компоненті.

Коли ми додаємо ребро, що об'єднує дві компоненти, то ми його завжди можемо додати. Інакше, треба перевірити парність відстані до кореня, якщо однакова, то нічого не робимо, інакше розпочинаємо новий відрізок.

СНМ можна модифікувати й перераховувати відстань до кореня під час пошуку кореня. Коли дві компоненти об'єднуються, ми фактично додаємо ребро не $(a;b)$, а $(par[a];par[b])$. Тому треба сказати, що парність відстані від $par[a]$ до $par[b]$ дорівнює парності суми $dst[a]+dst[b]+1$.