曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5808: 光纤通信

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：39 Solved：16
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

农民John 想要用光纤连通他的N (1 ≤ N ≤ 1,000) 个牲口棚(编号1..N)。但是，牲口棚位于一个大池塘边, 他仅可以连通相邻的牲口棚。John不需要连通所有的牲口棚, 因为只有某些奶牛之间想要彼此通讯。在保证这些奶牛通讯的情况下，他想使用最少的光纤完成通信网构件工作。
给出想要通讯的成对奶牛的清单，要求求出最少需使用多少根光纤。

Input

第1行: 2个整数, N 和 P (想要通讯的奶牛对数, 1 ≤ P≤ 10,000)
第2..P+1行: 2个整数，描述想要通讯的两只奶牛的编号

Output

仅1行，即最少使用光纤数。

Sample Input Copy 

5 2
1 3
4 5

Sample Output Copy 

3