2007-day4-fiber-prob

光ファイバー網の整備 (Fiber)

時間制限 : 1sec / スタック制限 : 64MB / メモリ制限 : 64MB

　クロアチアでは国内の全ての都市を光ファイバー網で結ぶ計画が進行している．光ファイバーを用いた通信回線は極めて高品質かつ高速であり，複数の都市を経由していても，ほとんど速度が低下することなく，高速な通信を行うことができる．例えば，k 個の都市A₁, … ,A_k に対し，都市A_i とA_i+1 (1 ≦ i ≦ k - 1) の間に光ファイバーが敷設されていれば，都市A₁ とA_k の間で高速通信を行うことができる．
　クロアチア政府は，国全体に光ファイバー網を張り巡らせて，全ての都市と都市の間で高速通信が行えるようにしたいと考えている．ところが困ったことに，現在では，規制緩和の影響で複数の光ファイバー敷設業者が乱立しており，国全体の光ファイバー網がどうなっているのか誰も把握していない．そこで，各業者から提出された光ファイバーの敷設情報を元に，全ての都市と都市の間の高速通信を可能にするためには，あと何本の光ファイバーを新たに敷設する必要があるのかを調べることにした．
　光ファイバーの敷設情報が与えられたときに，全ての都市と都市の間で高速通信を可能にするために，あと何本の光ファイバーを新たに敷設する必要があるのかを求めるプログラムを作成せよ．

入力

入力ファイルfiber.in の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の間に光ファイバーが敷設されていることを意味する．