Info Winter Speed Code 2023 - Clasele XI-XII | Graf Par

Cerință

Se dă un graf neorientat cu $n$ noduri și $m$ muchii. Să se scoată cel mult o muchie din graf astfel încât numărul de noduri cu grad par să fie cât mai mare posibil.

Date de intrare

Pe prima linie se găsesc două numere întregi, $n$ și $m$, reprezentând numărul de noduri din graf. Pe următoarele $m$ noduri se află muchiile grafului.

Date de ieșire

Pe prima linie se va găsi un singur număr întreg, numărul maxim de noduri cu grad par din graf.

Restricții și precizări

• $1 \leq n \leq 100 \ 000$;
• $1 \leq m \leq 200 \ 000$;
• Nu există două muchii identice.

Exemplu

stdin

5 4
1 2
1 3
2 4
4 5

stdout

3