BZPRO

#2689. 堡垒

内存限制：128 MiB 时间限制：10 Sec
提交 提交记录 讨论

题目描述

有个国家，它的所有城市如下图被公路连成了一个环，依次编号为1..N。并且在这个环内有一些笔直的公路，每条公路连接两个城市。为了不发生交通事故，任意两条公路不会在中途相交。为了使城市之间的交通更便利，城市间会建尽可能多的公路，但两个城市之间最多建一条公路。
    现在因为有另一个国家想破坏这个国家的交通系统，所以我们需要在一些城市建堡垒，使每条公路都能被监督（在i城市建堡垒可以监督与i城市相邻的公路）。问你最少需要建多少个堡垒。

输入格式

第一行有一个正整数N，表示城市数。
接下来2*N-3行（环上有N条公路，环中有N-3条公路），每行两个正整数u、v，表示城市u与城市v之间有一条公路。

输出格式

仅有一行一个正整数，表示最少的堡垒数。

样例

样例输入


			
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

数据范围与提示



【样例说明】

在1、3、5、7号城市建堡垒即可。

【数据规模和约定】

30%的数据中：N<=1000。

100%的数据中：N<=100000。

BZPRO Powered by Remmina.
Github Repository