24164번 - 光ファイバー網の整備 (Fiber) 다국어

クロアチアでは国内の全ての都市を光ファイバー網で結ぶ計画が進行している．光ファイバー を用いた通信回線は極めて高品質かつ高速であり，複数の都市を経由していても，ほとんど速 度が低下することなく，高速な通信を行うことができる．例えば，k 個の都市 A₁, . . . , A_k に対 し，都市 A_i と A_i+1 (1 ≤ i ≤ k − 1) の間に光ファイバーが敷設されていれば，都市 A₁ と A_k の 間で高速通信を行うことができる．

クロアチア政府は，国全体に光ファイバー網を張り巡らせて，全ての都市と都市の間で高速 通信が行えるようにしたいと考えている．ところが困ったことに，現在では，規制緩和の影響 で複数の光ファイバー敷設業者が乱立しており，国全体の光ファイバー網がどうなっているの か誰も把握していない．そこで，各業者から提出された光ファイバーの敷設情報を元に，全て の都市と都市の間の高速通信を可能にするためには，あと何本の光ファイバーを新たに敷設す る必要があるのかを調べることにした．

光ファイバーの敷設情報が与えられたときに，全ての都市と都市の間で高速通信を可能にす るために，あと何本の光ファイバーを新たに敷設する必要があるのかを求めるプログラムを作 成せよ．

入力の1行目には，クロアチア国内の都市の個数n (1 ≤ n ≤ 10000) が書かれている．各都市には 1 から n までの番号が付けられている．2 行目には，敷設されて いる光ファイバーの本数を表す整数 m (1 ≤ m ≤ 30000) が書かれている．続く m 行 (3 行目 ～ m + 2 行目) は光ファイバーの敷設情報を表す．i + 2 行目 (1 ≤ i ≤ m) には 2 つの異なる整数 a_i, b_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i) が空白を区切りとして書かれている．これは，都市 a_i と都市 b_i の間に光ファイバーが敷設されていることを意味する．

出力は，標準出力に行うこと．全ての都市と都市の間で高速通信を可能にするため に新たに敷設が必要な光ファイバーの本数の最小値を出力せよ．もし，現在のままでも全ての 都市と都市の間で高速通信が可能な場合は，0 を出力せよ．

この入力例に対応する 8 個の都市間の光ファイバー網を図示すると，以下の通りである．

2 本の光ファイバーを新たに敷設すれば，全ての都市と都市の間で高速通信が可能になる．例 えば，都市 2 と 1，都市 6 と 4 の間に敷設すればよい．これが新たに必要な光ファイバーの本数 の最小値である．