Road Improvement

Time Limit : 1 sec, Memory Limit : 262144 KB

道路網改修

観光で有名な会津国には、それぞれ 0 から N-1 までの番号が割り当てられた N 個の都市があり、2つの都市を結ぶ一方通行のM 本の道路で道路網が形成されている。

会津国では、都市を結ぶすべての道路沿いに桜並木がある。観光客に桜を楽しんでもらえるように、すべての道路を巡ることができるような道路網に改修したい。そのため、以下の条件を満たすように2つの都市を直接結ぶ道路を何本か増設することにした。

  • 増設する道路は、一方通行のものに限る。
  • 任意の都市から出発したとき、増設したものも含めて国内のすべての道路を1度以上通って出発した都市に戻ることができる。

会津国の観光推進担当者であるあなたは、プログラムを作成して道路建設計画を立てることになった。

会津国の都市と道路の情報が与えられたとき、増設しなければならない道路の数の最小値を出力するプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

N M
s_1 t_1
s_2 t_2
:
s_M t_M

1行目に都市の数 N (1 ≤ N ≤ 104)、道路の数 M (0 ≤ M ≤ 105) が与えられる。続くM 行に、i 番目の道路が結ぶ始点と終点の都市の番号 s_i, t_i (0 ≤ s_i, t_iN-1) が与えられる(s_i ≠ t_i)。ただし、同じ道路は2回以上与えられない。

Output

増設する道路の数の最小値を1行に出力する。

Sample Input 1

6 7
0 2
2 1
1 0
2 3
4 3
4 5
5 4

Sample Output 1

2

Sample Input 2

6 9
0 2
2 1
1 0
2 3
4 3
4 5
5 4
5 2
3 4

Sample Output 2

0

Source: PC Koshien 2017 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2017-9-9
http://web-ext.u-aizu.ac.jp/pc-concours/