問題
観光で有名な会津国には、それぞれ 0 から N-1 までの番号が割り当てられた N 個の都市があり、２つの都市を結ぶ一方通行の M 本の道路で道路網が形成されている。
会津国では、都市を結ぶすべての道路沿いに桜並木がある。観光客に桜を楽しんでもらえるように、すべての道路を巡ることができるような道路網に改修したい。そのため、以下の条件を満たすように２つの都市を直接結ぶ道路を何本か増設することにした。
- 増設する道路は、一方通行のものに限る。
- 任意の都市から出発したとき、増設したものも含めて国内のすべての道路を１度以上通って出発した都市に戻ることができる。
会津国の観光推進担当者であるあなたは、プログラムを作成して道路建設計画を立てることになった。
課題
会津国の都市と道路の情報が与えられたとき、増設しなければならない道路の数の最小値を出力するプログラムを作成せよ。
入力
入力は以下の形式で与えられる。
N M s1 t1 s2 t2 : sM tM１行目に都市の数 N(1≦N≦104)、道路の数 M(0≦M≦105)が与えられる。
続く M 行に、i 番目の道路が結ぶ始点と終点の都市の番号 si,ti(0≦si,ti≦N-1)が与えられる(si≠ti)。
ただし、同じ道路は２回以上与えられない。
出力
増設する道路の数の最小値を１行に出力する。
入出力例
入力例1
6 7 0 2 2 1 1 0 2 3 4 3 4 5 5 4出力例1
2
入力例2
6 9 0 2 2 1 1 0 2 3 4 3 4 5 5 4 5 2 3 4出力例2
0