光纤通信 - Problem

#22809. 光纤通信

Statistics

Farmer John 想用新光纤网络连接 $N$ 座谷仓（$1 \le N \le 1{,}000$），编号 $1..N$。谷仓沿大池塘边围成一圈，因此只能连接相邻谷仓；谷仓 $N$ 与 1 相邻。

不需要连通全部谷仓，因为只有特定牛对想通信。他希望连接尽量少，又让所有需求对通过网络通信。给定这些谷仓对，求至少铺设多少线路。从谷仓 1 到 3 通信，要铺设 1 到 2、2 到 3 的线路。

输入格式

第 $1$ 行：整数 $N$、$P$，后者为通信对数（$1 \le P \le 10{,}000$）。
第 $2..P+1$ 行：两个整数，表示希望通信的一对谷仓；列表没有重复对。

输出格式

一行一个整数，FJ 所需最少直接连接数。

样例

输入格式 1

5 2
1 3
4 5

输出格式 1

说明

这些线路连接谷仓对 1-2、2-3、4-5。

题目来源：Reid Barton，2001。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0

No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
Do not submit duplicated issues.
Issues must be filed in English or Chinese only.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0