[[原文:http://poj.org/problem?id=1944]] 
----
''時間制限'':1000ミリ秒
''メモリ制限'':30000KB
&br;

*問題 [#cfd64d6a]
農夫ジョンは、彼の N (1 <= N <= 1,000) 個の納屋を新しい光ファイバー網で繋ぎたいと思っている。納屋には 1 から N まで順に番号が付けられている。しかし、納屋は大きい池の端に円状に位置しているため（つまり、納屋 N は納屋 1 とも隣接している）、彼は互いに隣接している納屋をつなぐことしかできない。

しかし、互いに通信したいと思っている牛の組は限られているため、ジョンはすべての納屋をつなぐ必要はない。彼は、できるだけ少ない数の接続で、通信したいすべての牛の組が光ファイバー網を用いて通信できるようにしたい。
互いに通信できる必要のある納屋の組のリストが与えられた時、引かれる通信線の数の最小値を決定せよ。例えば、納屋 1 から 3 まで通信したいとき、通信線を納屋 1-2, 2-3 に引く必要がある。或いは、N=3 のときは単に納屋 3-1 に引くだけもでよい。

*入力 [#afb9861f]
1 行目：2 つの自然数 N, P (1 <= P <= 10,000)。P は通信するペアの数を表す。
2 ～ P+1 行目：互いに通信したいと思っている納屋の組を表す 2 つの整数。入力中に同じ組が複数回現れることはない。

*出力 [#j4cda4cb]
ジョンがつなぐ必要のある通信線の最小数を表す整数のみを含む 1 行を出力せよ。

*入力の例 [#d959ea95]
 5 2
 1 3
 4 5

*出力の例 [#tb58a346]
 3

* ヒント [#wb6e39ed]
入力例では、納屋 1-2, 2-3, 4-5 に通信線を引けばよい。

*出典 [#p8da5a11]
USACO 2002 February