Friend Palindrome

Jaehong is an elementary school student. At this spring's school show he takes the conductor's part and his classmates dance. The dance goes like this. The friends on stage stand in a single line and each one freestyles, then, taking the middle of the line as the reference point, the friend on the left and the friend on the right join both hands and dance together. If five friends stand in a line, the first and the fifth dance together, and the second and the fourth dance together. The third friend has nobody left to dance with, so that friend does a robot dance alone.

Every classmate wants to dance only with a close friend. 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 send onto the stage and tell Jaehong. Friends are identified by roll number, numbered from 1 to $N$. 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 friend doing the robot dance, every friend on stage must be paired with a close friend. Any classmate can do the robot dance.

The first line contains the number of classmates $N$ and the number of friendships $M$ ($2 \le N \le 20$, $0 \le M \le \min((N^2 - N)/2,\ 50)$). Jaehong is not counted in $N$. 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.

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

Print the largest number of friends that can stand on the stage.