网络安全一直是非常重要的一件事情，现在太空观测基地里的机房所有主机都用网线相连，如图所示，主机编号为1..N。在这个环内有一些额外的网线直接连接两台主机。为了机房网线布线合理，任意两条网线中途不能相交。为了使主机之间的网络更加通畅，主机之间会尽可能的相连，但两台主机之间最多连接一条网线。
现在想测试这个机房网络系统的安全性能，需要在一些主机上安装监测软件，使每条网线都能被检测（在第i号主机安装监测软件可以监测与它直接相连的网线）。请问最少需要在多少台主机上安装监测软件。
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $0$ | 正确数量 | $0$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 |
网络安全一直是非常重要的一件事情，现在太空观测基地里的机房所有主机都用网线相连，如图所示，主机编号为1..N。在这个环内有一些额外的网线直接连接两台主机。为了机房网线布线合理，任意两条网线中途不能相交。为了使主机之间的网络更加通畅，主机之间会尽可能的相连，但两台主机之间最多连接一条网线。
现在想测试这个机房网络系统的安全性能，需要在一些主机上安装监测软件，使每条网线都能被检测（在第i号主机安装监测软件可以监测与它直接相连的网线）。请问最少需要在多少台主机上安装监测软件。
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1
1 3
8 3
7 3
7 5
5 3
4