Friend Palindrome 2

Jaehong is an elementary school student. At this spring's school show he conducts while his classmates dance. The dance goes like this. The friends on stage first stand in a single line and each one improvises alone. Then, taking the middle of the line as the center, the $i$-th friend from the left and the $i$-th friend from the right take each other's hands and dance together. With five friends in line, the first and the fifth form a pair and the second and the fourth form a pair. The third friend, standing in the middle, has no partner, so that friend does a robot dance alone. One friend dances alone like this only when the number of friends on stage is odd.

Every classmate wants a partner who is a close friend, and wants a partner of the opposite sex. A boy must hold hands with a girl and a girl must hold hands with a boy. Jaehong wants a big show, so he puts as many friends on stage as he can. Given the friendships, find the largest number of friends he can put on stage and tell him. Friends are identified by roll numbers $1$ through $N$, and each friend has exactly one roll number.

Even if A and B are close friends and B and C are close friends, A and C are not necessarily close friends. Apart from the one friend doing the robot dance, everyone on stage must be paired with a close friend of the opposite sex. Any classmate can do the robot dance.

The first line contains the number of classmates $N$ and the number of friendships $M$, separated by a space. Jaehong is not counted. ($2 \le N \le 200$, $0 \le M \le \min((N^2-N)/2, 10000)$)

Each of the next $M$ lines contains one friendship as two roll numbers $u$ and $v$. $u$ and $v$ are different, and if $u$ and $v$ are close friends then $v$ and $u$ are close friends too. An odd roll number belongs to a girl and an even roll number belongs to a boy.

The same friendship is never given more than once. If 1 2 has already appeared, neither 1 2 nor 2 1 appears again.

Print the largest number of friends that can go on stage, on one line.