Спершу перекладемо «властивість непарності» звичною мовою теорії графів. Замкнутий шлях C_1, \ldots, C_K з C_1 = C_K має довжину (кількість елементів послідовності), а ребер у ньому K - 1. Вимога, щоб була непарною, означає, що будь-який цикл має парну кількість ребер. А граф, у якому всі цикли парні, — це в точності дводольний граф.
Отже, треба додати якнайбільше ребер, зберігши дводольність (і простоту графа).
Дводольний граф — це розбиття вершин на дві частки так, що всі ребра йдуть між частками. Якщо в частках і вершин відповідно та , то максимальна кількість ребер — це повний дводольний граф, тобто |A| \cdot |B|. Тому відповідь дорівнює
Залишилось зрозуміти, які розбиття взагалі досяжні. Усередині кожної компоненти зв'язності розфарбування в два кольори визначено однозначно з точністю до обміну кольорів. Тому для компоненти з розмірами часток (c_1, c_2) ми вільні віднести до або c_1, або c_2 вершин — незалежно від інших компонент. Ізольовані вершини дають вибір .
Звідси алгоритм:
обходом у глибину (або ширину) розфарбуємо кожну компоненту у два кольори й запам'ятаємо пару (c_1, c_2);
задачею про рюкзак з'ясуємо, які значення досяжні: булева динаміка — чи можна набрати рівно вершин у першу частку, беручи з кожної компоненти або c_1, або c_2;
серед досяжних візьмемо той, що максимізує s \cdot (N - s), тобто найближчий до ;
віднімемо вже наявні ребер.
Динаміку зручно реалізувати бітовою множиною (bitset у C++), і тоді крок для компоненти — це два зсуви та побітове АБО. Складність — \mathcal{O}(N^2/64 + M), що при N \le 10^4 цілком швидко.
Добуток |A| \cdot |B| сягає 2.5 \cdot 10^7, тому переповнення не загрожує, але 64-бітний тип не завадить.