観光で有名な会津国には、それぞれ 0 から N-1 までの番号が割り当てられた N 個の都市があり、2つの都市を結ぶ一方通行のM 本の道路で道路網が形成されている。
会津国では、都市を結ぶすべての道路沿いに桜並木がある。観光客に桜を楽しんでもらえるように、すべての道路を巡ることができるような道路網に改修したい。そのため、以下の条件を満たすように2つの都市を直接結ぶ道路を何本か増設することにした。
会津国の観光推進担当者であるあなたは、プログラムを作成して道路建設計画を立てることになった。
会津国の都市と道路の情報が与えられたとき、増設しなければならない道路の数の最小値を出力するプログラムを作成せよ。
入力は以下の形式で与えられる。
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_i ≤ N-1) が与えられる(s_i ≠ t_i)。ただし、同じ道路は2回以上与えられない。
増設する道路の数の最小値を1行に出力する。
6 7 0 2 2 1 1 0 2 3 4 3 4 5 5 4
2
6 9 0 2 2 1 1 0 2 3 4 3 4 5 5 4 5 2 3 4
0