0396 - リングと紐

Problem Statement

芸術家のみさわさんは新しい作品を作ろうとしている． 新しい作品の材料として，みさわさんは金属の輪と白黒2色の紐を大量に用意した． みさわさんは，異なる 2 つの輪をいずれかの色の紐で結ぶことを繰り返すことによって作品を作ることが出来る． 1 つの輪を複数の輪と繋ぐことも可能であるが，それぞれの輪のペアを結ぶ紐は高々 1 本である． みさわさんは，せっかく作品を作るからにはよい作品を作りたいと考えた． みさわさんの考える「よい作品」とは，以下のように定義されるものである．

• 1 つの輪は 1 つのよい作品である．
• 2 つのよい作品を用意したとき，それらに含まれている紐で繋がれていない輪のペア全てを白い紐で繋いだものは， 1 つのよい作品である．(図1. 操作1)
• よい作品の白い紐を黒い紐に，黒い紐を白い紐にすべて入れ替えたものはよい作品である．(図1. 操作2)
• 以上で定義されたもののみがよい作品である．

図 1 はよい作品の一例である．

図 1. よい作品の例

以上の条件を満たすような渾身の「よい作品」を作り上げたみさわさんは，この作品に含まれる 0 個以上の輪を選び，それらを天井から吊るして展示することにした． このとき，なるべく黒い紐が映えるように展示したい． すなわち，天井から吊るされている輪とそれ以外の輪の間を繋ぐ黒い紐の本数が最大になるようにしたい．

そのように展示した時の，天井から吊るされている輪とそれ以外の輪の間を繋ぐ黒い紐の本数を求めよ．

Input

入力は以下のような形式で与えられる．

N M
u1 v1
:
uM vM

N (1 ≤ N ≤ 5 000) は作品に含まれる輪の数である． M (1 ≤ M ≤ 100 000) は作品に含まれる黒い紐の本数である．

u_i, v_i (1 ≤ u_i, v_i ≤ N)は i 番目の黒い紐が u_i 番目の輪と v_i 番目の輪を繋いでいることを表す． 入力で指定されなかった輪のペアに関しては白い紐で繋がれている． 入力で与えられる作品は「よい作品」であることが保証されている．

Output

天井から吊るされている輪とそれ以外の輪の間を繋ぐ黒い紐の本数の最大値を求めよ．

Sample Input 1

5 4
1 2
2 3
3 1
4 5

Output for the Sample Input 1

3

Sample Input 2

6 5
1 2
1 3
1 4
1 5
3 4

Output for the Sample Input 2

4

Sample Input 3

5 8
2 5
5 4
1 3
1 5
4 1
2 4
3 4
3 2

Output for the Sample Input 3

6