新規
編集
添付
時間制限:1000ミリ秒
メモリ制限:30000KB
問題 
農夫ジョンは、彼の N (1 <= N <= 1,000) 個の納屋を新しい光ファイバー網で繋ぎたいと思っている。納屋には 1 から N まで順に番号が付けられている。しかし、納屋は大きい池の端に円状に位置しているため（つまり、納屋 N は納屋 1 とも隣接している）、彼は互いに隣接している納屋をつなぐことしかできない。
しかし、互いに通信したいと思っている牛の組は限られているため、ジョンはすべての納屋をつなぐ必要はない。彼は、できるだけ少ない数の接続で、通信したいすべての牛の組が光ファイバー網を用いて通信できるようにしたい。
互いに通信できる必要のある納屋の組のリストが与えられた時、引かれる通信線の数の最小値を決定せよ。例えば、納屋 1 から 3 まで通信したいとき、通信線を納屋 1-2, 2-3 に引く必要がある。或いは、N=3 のときは単に納屋 3-1 に引くだけもでよい。
入力
1 行目：2 つの自然数 N, P (1 <= P <= 10,000)。P は通信するペアの数を表す。
2 ～ P+1 行目：互いに通信したいと思っている納屋の組を表す 2 つの整数。入力中に同じ組が複数回現れることはない。
出力
ジョンがつなぐ必要のある通信線の最小数を表す整数のみを含む 1 行を出力せよ。
入力の例
5 2 1 3 4 5
出力の例
3
ヒント
入力例では、納屋 1-2, 2-3, 4-5 に通信線を引けばよい。
出典
USACO 2002 February
