/
実行時間制限: 1 sec / メモリ制限: 64 MiB
AtCoder での提出方法
標準入力から入力を読み込み,標準出力へ出力すること.
配点 : 100 点
問題文
クロアチアでは国内の全ての都市を光ファイバー網で結ぶ計画が進行している.光ファイバーを用いた通信回線は極めて高品質かつ高速であり,複数の都市を経由していても,ほとんど速度が低下することなく,高速な通信を行うことができる.例えば,k 個の都市 A_1, \ldots, A_k に対し,都市 A_i と A_{i+1} (1 \leqq i \leqq k - 1) の間に光ファイバーが敷設されていれば,都市 A_1 と A_k の間で高速通信を行うことができる.
クロアチア政府は,国全体に光ファイバー網を張り巡らせて,全ての都市と都市の間で高速通信が行えるようにしたいと考えている.ところが困ったことに,現在では,規制緩和の影響で複数の光ファイバー敷設業者が乱立しており,国全体の光ファイバー網がどうなっているのか誰も把握していない.そこで,各業者から提出された光ファイバーの敷設情報を元に,全ての都市と都市の間の高速通信を可能にするためには,あと何本の光ファイバーを新たに敷設する必要があるのかを調べることにした.
光ファイバーの敷設情報が与えられたときに,全ての都市と都市の間で高速通信を可能にするために,あと何本の光ファイバーを新たに敷設する必要があるのかを求めるプログラムを作成せよ.
入力
入力の 1 行目には,クロアチア国内の都市の個数 n (1 \leqq n \leqq 10000) が書かれている.各都市には 1 から n までの番号が付けられている.2 行目には,敷設されている光ファイバーの本数を表す整数 m (1 \leqq m \leqq 30000) が書かれている.続く m 行 (3 行目~m + 2 行目) は光ファイバーの敷設情報を表す.i + 2 行目 (1 \leqq i \leqq m) には 2 つの異なる整数 a_i, b_i (1 \leqq a_i, b_i \leqq n, a_i \neq b_i) が空白を区切りとして書かれている.これは,都市 a_i と都市 b_i の間に光ファイバーが敷設されていることを意味する.
出力
出力は,標準出力に行うこと.全ての都市と都市の間で高速通信を可能にするために新たに敷設が必要な光ファイバーの本数の最小値を出力せよ.もし,現在のままでも全ての都市と都市の間で高速通信が可能な場合は,0 を出力せよ.
入力例 1
8 7 3 5 4 1 5 4 7 5 4 7 1 4 6 8
出力例 1
2
この入力例に対応する 8 個の都市間の光ファイバー網を図示すると,以下の通りである.
2 本の光ファイバーを新たに敷設すれば,全ての都市と都市の間で高速通信が可能になる.例えば,都市 2 と 1,都市 6 と 4 の間に敷設すればよい.これが新たに必要な光ファイバーの本数の最小値である.