친구 팰린드롬 2

초등학생 재홍이는 이번 봄 학예회에서 지휘를 맡고, 반 친구들이 춤을 추기로 했다. 춤은 이렇게 진행된다. 무대에 오른 친구들이 먼저 일렬로 서서 각자 막춤을 추다가, 줄의 한가운데를 기준으로 왼쪽에서 $i$번째에 선 친구와 오른쪽에서 $i$번째에 선 친구가 두 손을 마주 잡고 함께 춤을 춘다. 친구 다섯 명이 일렬로 서 있다면 첫 번째와 다섯 번째가 짝이 되고, 두 번째와 네 번째가 짝이 된다. 가운데에 선 세 번째 친구는 짝이 없으므로 혼자 로봇 댄스를 춘다. 무대에 오른 인원이 홀수일 때만 이렇게 혼자 추는 친구가 한 명 생긴다.

반 친구들은 서로 친한 친구하고만 짝이 되고 싶어 하고, 이성 친구하고만 짝이 되고 싶어 한다. 남자아이는 여자아이와, 여자아이는 남자아이와 손을 잡아야 한다. 재홍이는 무대를 크게 꾸미고 싶어서 최대한 많은 친구를 올리려고 한다. 친구 관계가 주어질 때 무대에 올릴 수 있는 최대 인원을 구해 재홍이에게 알려주자. 친구는 $1$번부터 $N$번까지의 출석번호로 구분하며, 한 친구는 출석번호를 하나만 갖는다.

A와 B가 친한 친구이고 B와 C가 친한 친구여도, A와 C가 친한 친구라는 보장은 없다. 로봇 댄스를 추는 한 명을 빼면 무대에 오른 친구는 모두 자신과 친한 이성 친구와 짝을 이뤄야 한다. 로봇 댄스는 반 친구 누구나 출 수 있다.

첫째 줄에 반 친구 수 $N$과 친구 관계 수 $M$이 공백으로 구분되어 주어진다. 재홍이는 인원에서 제외한다. ($2 \le N \le 200$, $0 \le M \le \min((N^2-N)/2, 10000)$)

둘째 줄부터 $M$개 줄에 걸쳐 친한 친구 관계가 출석번호 $u$와 $v$로 한 줄에 하나씩 주어진다. $u$와 $v$는 서로 다르고, $u$와 $v$가 친한 친구이면 $v$와 $u$도 친한 친구다. 출석번호가 홀수면 여자아이, 짝수면 남자아이다.

같은 관계는 두 번 이상 주어지지 않는다. 1 2가 이미 나왔다면 1 2도 2 1도 다시 나오지 않는다.

무대에 올릴 수 있는 친구 수의 최댓값을 한 줄에 출력한다.