고리와 끈

예술가 미사와 씨는 새 작품을 만들려고 한다. 미사와 씨는 금속 고리와 흑백 두 가지 색의 끈을 대량으로 준비했다.

미사와 씨는 서로 다른 두 고리를 어느 색이든 끈으로 묶는 일을 반복해서 작품을 만들 수 있다. 한 고리를 여러 고리와 이을 수도 있지만, 고리 쌍마다 끈은 많아야 한 개다.

미사와 씨는 작품을 만드는 김에 좋은 작품을 만들고 싶어 한다. 미사와 씨가 생각하는 '좋은 작품'은 다음과 같이 정의된다.

• 고리 하나는 좋은 작품 하나다.
• 좋은 작품 두 개를 준비했을 때, 두 작품에 각각 들어 있는 끈으로 이어지지 않은 고리 쌍을 모두 흰 끈으로 이은 것은 좋은 작품 하나다. (그림 1. 조작 1)
• 좋은 작품의 흰 끈을 검은 끈으로, 검은 끈을 흰 끈으로 모두 바꾼 것은 좋은 작품이다. (그림 1. 조작 2)
• 위에서 정의된 것만이 좋은 작품이다.

그림 1은 좋은 작품의 한 예다.

그림 1. 좋은 작품의 예

미사와 씨는 위 조건을 모두 만족하는 정성껏 만든 '좋은 작품'을 완성했다. 미사와 씨는 이 작품에 포함된 0개 이상의 고리를 골라 천장에 매달아 전시하기로 했다. 이때 검은 끈이 돋보이도록 전시하고 싶다. 즉, 천장에 매달린 고리와 그렇지 않은 고리 사이를 잇는 검은 끈의 개수가 최대가 되도록 하고 싶다.

이렇게 전시했을 때, 천장에 매달린 고리와 그렇지 않은 고리 사이를 잇는 검은 끈의 개수를 구하라.

입력은 다음 형식으로 주어진다.

$N$ $M$

$u_1$ $v_1$

...

$u_M$ $v_M$

$N$ ($1 \leq N \leq 5000$)은 작품에 포함된 고리의 개수다. $M$ ($1 \leq M \leq 100000$)은 작품에 포함된 검은 끈의 개수다.

$u_i$, $v_i$ ($1 \leq u_i, v_i \leq N$)는 $i$번째 검은 끈이 $u_i$번 고리와 $v_i$번 고리를 잇고 있음을 뜻한다. 입력에 주어지지 않은 고리 쌍은 흰 끈으로 이어져 있다. 입력으로 주어지는 작품은 '좋은 작품'임이 보장된다.

천장에 매달린 고리와 그렇지 않은 고리 사이를 잇는 검은 끈 개수의 최댓값을 출력하라.